Linear Search là gì

Cho trước một danh sách gồm n phần tử. Bài toán tìm kiếm là bài toán tìm phần tử x có giá trị cho trước trong danh sách. Nếu phần tử đó tồn tại trong danh sách thì xuất vị trí của nó trong danh sách. Nếu phần tử đó không tồn tại trong danh sách thì xuất thông báo không tìm thấy.

Chúng ta có thể phát biểu bài toán như sau:

– Đầu vào (input):

• • Một danh sách gồm n phần tử a0,a1,a2,…,an-1. Thường dùng mảng một chiều để lưu danh sách này.
  • Phần tử cần tìm là x.

– Đầu ra (output): Nếu tìm được phần tử x ở vị trí thứ k trong danh sách thì xuất kết quả là k, ngược lại nếu không tìm thấy thì xuất kết quả là –1.

Có 2 thuật toán tìm kiếm thường được sử dụng là:

• • Thuật toán tìm kiếm tuyến tính (Linear Search)
  • Thuật toán tìm kiếm nhị phân (Binary Search)

Còn gọi là tìm kiếm tuần tự. Ý tưởng của thuật toán này như sau:

So sánh x lần lượt với phần tử thứ 1, thứ 2,…của danh sách cho đến khi gặp được phần tử cần tìm. Nếu tìm hết mảng mà không thấy thì xuất thông báo không tìm thấy.

Các bước của thuật toán:

Bước 1: Gán i = 0; //bắt đầu từ phần tử đầu tiên của mảng

Bước 2: So sánh a[i] với x, 2 khả năng có thể xảy ra:

            + a[i] == x: Tìm thấy -> Xuất kết quả là i -> Dừng.

            + a[i] !=x: Chuyển qua Bước 3.

Bước 3: i = i + 1; //xét tiếp phần tử kế tiếp trong mảng

            Nếu i == n : Hết mảng -> không tìm thấy -> Dừng.

            Ngược lại: Lặp lại Bước 2.

Minh họa thuật toán tìm kiếm tuyến tính

Tìm phần tử x=1 trong mảng bên dưới.

Lần lượt so sánh x với các phần tử trong mảng.

Tìm được x trong mảng.

Cài đặt thuật toán tìm kiếm tuyến tính với C++

Hàm LinearSearch() trả về i là vị trí của x trong mảng nếu tìm thấy x, ngược lại trả về -1.

int LinearSearch(int a[], int n, int x) { int i=0; while((i

Nhận xét:

Thuật toán tìm kiếm tuyến tính sử dụng 2 phép so sánh là i. Trường hợp xấu nhất, mỗi phép so sánh này đều có thể thực hiện n lần. Do đó, số phép so sánh của thuật toán trong trường hợp xấu nhất là 2*n. Độ phức tạp của thuật toán là O(n).

Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán, ta thêm phần tử “lính canh” vào cuối danh sách. Cùng xem cải thiết của thuật toán bên dưới.

Cài đặt thuật toán tìm kiếm tuyến tính cải tiến với C++

int LinearSearch(int a[], int n, int x){ int i=0; a[n]=x; //a[n] là phần tử “lính canh” while(a[i]!=x){ i++; } if(i==n){ return -1; //Tìm không thấy x } else{ return i; //Tìm thấy x } }

Ý tưởng:

Gán phần tử a[n]=x, mảng a có thêm phần tử cuối cùng là x. Do đó, khi tìm x trong mảng a thì chắc chắn sẽ tìm thấy. Nhưng nếu tìm thấy x ở vị trí cuối cùng n thì coi như không tìm thấy x. Nếu tìm thấy x ở vị trí khác n (từ 0 đến n-1) thì có nghĩa là tìm thấy x.

Nhận xét:

Thuật toán tìm kiếm tuyến tính cải tiến chỉ sử dụng 1 phép so sánh a[i]!=x. Trường hợp xấu nhất, số phép so sánh của thuật toán là n. Tức là giảm được phân nữa phép so sánh của thuật toán tìm kiếm thông thường.

Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Linear Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Linear Search thông qua các phần sau.

1. Giới thiệu

Bài toán: Cho một mảng arr [] gồm n phần tử, hãy viết hàm tìm kiếm một phần tử x cho trước trong arr [].

Ví dụ:

Đầu vào: arr [] = {10, 20, 80, 30, 60, 50,

110, 100, 130, 170}

x = 110;

Đầu ra: 6

Nguyên tố x hiện diện ở chỉ số 6

Đầu vào: arr [] = {10, 20, 80, 30, 60, 50,

110, 100, 130, 170}

x = 175;

Đầu ra: -1

Phần tử x không có trong arr [].

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), tức là

• Bắt đầu từ phần tử ngoài cùng bên trái của arr [] và lần lượt so sánh x với từng phần tử của arr []
• Nếu x khớp với một phần tử, trả về chỉ mục.
• Nếu x không khớp với bất kỳ phần tử nào, trả về -1.

2. Code ví dụ trên nhiều ngôn ngữ khác

C++

// C++ code to linearly search x in arr[]. If x // is present then return its location, otherwise // return -1 #include using namespace std; int search(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = search(arr, n, x); (result == -1)? cout<<"Element is not present in array" : cout<<"Element is present at index " <C

// C code to linearly search x in arr[]. If x // is present then return its location, otherwise // return -1 #include int search(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = search(arr, n, x); (result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result); return 0; }

Java

// Java code for linearly searching x in arr[]. If x // is present then return its location, otherwise // return -1 class GFG { public static int search(int arr[], int x) { int n = arr.length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int result = search(arr, x); if(result == -1) System.out.print("Element is not present in array"); else System.out.print("Element is present at index " + result); } }

Python3

# Python3 code to linearly search x in arr[]. # If x is present then return its location, # otherwise return -1 def search(arr, n, x): for i in range (0, n): if (arr[i] == x): return i; return -1; # Driver Code arr = [ 2, 3, 4, 10, 40 ]; x = 10; n = len(arr); result = search(arr, n, x) if(result == -1): print("Element is not present in array") else: print("Element is present at index", result);

C#

// C# code to linearly search x in arr[]. If x // is present then return its location, otherwise // return -1 using System; class GFG { public static int search(int[] arr, int x) { int n = arr.Length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } public static void Main() { int[] arr = { 2, 3, 4, 10, 40 }; int x = 10; int result = search(arr, x); if(result == -1) Console.WriteLine("Element is not present in array"); else Console.WriteLine("Element is present at index "+ result); } }

PHP

Kết quả

Element is present at index 3

3. Độ phức tạp

Độ phức tạp thời gian của thuật toán trên là O (n).

Tìm kiếm tuyến tính(Linear Search) hiếm khi được sử dụng thực tế vì các thuật toán tìm kiếm khác như thuật toán tìm kiếm nhị phân(binary search) và bảng băm(hash tables) cho phép so sánh tìm kiếm nhanh hơn đáng kể so với tìm kiếm tuyến tính.

Nguồn và Tài liệu tiếng anh tham khảo:

• w3schools
• Geeksforgeeks
• codechef
• dev.to

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!