Tìm kiếm tuyến tính – Linear Search

Giới thiệu

Tìm kiếm tuyến tính (hay còn gọi là tìm kiếm tuần tự) là một phương pháp để tìm kiếm một phần tử trong danh sách. Nó sẽ kiểm tra tuần tự tất cả các phần tử trong danh sách cho đến khi nào tìm ra phần tử đó thì trả về, nếu không thì việc tìm kiếm sẽ tiếp tục cho đến khi kết thúc tìm kiếm.

Cài đặt

Bước 1: Bắt đầu từ phần tử trái nhất của mảng và so sánh từng phần tử trong mảng với phần tử cần tìm

Bước 2: Nếu phần tử nào trùng với phần tử cần tìm thì trả về chỉ số của phần tử đó trong mảng

Bước 3: Nếu không có phần tử nào trùng thì trả về -1

class LS
{  
     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); 
     } 
} 

Kết quả:

Element is present at index 3

Đánh giá thuật toán

Độ phức tạp thuật toán: O(n)

Cách sử dụng: Tìm kiếm tuyến tính là một thuật toán đơn giản, rất dễ cho người mới học lập trình và dễ cài đặt. Tuy nhiên, trên thực tế nó rất hiếm khi được sử dụng vì có nhiều thuật toán khác (VD: tìm kiếm nhị phân, bảng băm,…) cho kết quả tìm kiếm nhanh hơn đáng kể so với tìm kiếm tuyến tính.