Học Java

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.

>> Xem ngay Tài liệu Java Core giúp bạn “Nâng Cấp” kỹ năng lập trình

Cài đặt

Linear Search Animation

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.

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Tài liệu + Khóa học lập trình FREE
Tài liệu + Khóa học lập trình FREE

DMCA.com Protection Status