Thuật toán Tìm kiếm Nhị Phân

10-08-2022

Tìm kiếm là một phần không thể thiếu của mọi ứng dụng, website hay phần mềm. Tính năng tìm kiếm cho phép người sử dụng nhanh chóng truy vấn và tìm kiếm các bản ghi theo mong muốn. Nhưng không phải phép tìm kiếm nào cũng hiệu quả và nhanh chóng. Bài viết này chúng ta sẽ cùng tìm hiểu về thuật toán tìm kiếm hiệu quả được nhiều các lập trình viên lựa chọn: Tìm kiếm nhị phân

Ngày 24/7 vừa qua, bộ Giáo dục và Đào tạo đã công bố điểm thi tốt nghiệp THPT năm 2022 của hơn 1 triệu sĩ tử trên cả nước. Các sĩ tử có thể sử dụng những công cụ tìm kiếm được cung cấp để kiểm tra điểm của mình một cách nhanh chóng dựa vào số báo danh. Giả sử bạn muốn kiểm tra điểm của một thí sinh trong danh sách, nếu chương trình của công cụ bạn đang dùng kiểm tra số báo danh trong danh mục theo thứ tự bắt đầu, với thuật toán tìm kiếm tuyến tính, máy tính có thể phải kiếm tra tất cả hơn 1 triệu số bao danh, trong trường hợp xấu nhất. Nếu danh mục được sắp xếp, với tìm kiếm nhị phân sẽ không phải kiếm tra hơn 20 lần để tìm ra thông tin số báo danh mà bạn cần.

Bài viết sẽ tiếp tục với thông tin và cách hoạt động của thuật toán tìm kiếm nhị phân.

Chúng ta cùng tìm hiểu nhé!

Bắt đầu nào!

TÌM KIẾM NHỊ PHÂN

Tên tiếng Anh là Binary Search, là một thuật toán tìm kiếm được sử dụng rất nhiều trong thực tế, dùng để xác định vị trí giá trị cần tìm trong một mảng đã được sắp xếp.

Ý tưởng

  • Thuật toán ban đầu yêu cầu mảng đã được sắp xếp.
  • Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng. Lúc này mảng sẽ được chia ra làm 2 phần bên trái và bên phải phần tử đó.
  • Nếu chúng không bằng nhau, phần nửa mảng không chứa giá trị cần tìm sẽ bị bỏ qua và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa và so sánh với giá trị cần tìm, cứ thế lặp lại cho đến khi tìm thấy giá trị đó.
  • Nếu tìm kiếm kết thúc khi nửa còn lại trống thì ta kết luận giá trị không có trong mảng.

Có vẻ vẫn còn hơi khó hình dung, để hiểu rõ hơn về thuật toán, chúng ta sẽ tới các bước thực hiện sau đây nhé!

Các bước thực hiện tìm kiếm

Chú ý: Bài viết sử dụng mảng arr [ ] đã được sắp xếp tăng dần. Sau khi hiểu thuật toán, các bạn sẽ có thể tự làm được với mảng sắp xếp giảm dần

Bước 1: Gán left = 0 và right = n – 1 (vị trí đầu và cuối của mảng).

Bước 2: Gán mid = (left + right)/2 (vị trí giữa của mảng hiện hành).

  So sánh mid arr[mid] và x:

  • arr [mid] = x => Tìm thấy x. Dừng chương trình.
  • arr [mid] > x => Gán right = mid - 1.
  • arr [mid] < x => Gán left = mid + 1.

Bước 3: Nếu left <= right thì ta lặp lại bước 2. Ngược lại, sẽ dừng chương trình.

Thực hiện Code 

Chương trình được thực hiện trên ngôn ngữ C, và tìm kiếm phần tử có giá trị 55 trong mảng arr [ ] đã sắp xếp tăng dần

Và sử dụng vòng lặp While với điều kiện vòng lặp là left <= right

Nếu không tìm thấy giá trị cần tìm trong mảng thì sẽ return -1

 int binarySearch(int arr[ ], int n, int key)
   {
       int left, right, mid;
       left = 0;
       right = n-1;
       while(left <= right)
       {
           mid = (left + right)/2;
           if(arr[mid] == key)
           {
               return mid;
           }
           else if(arr[mid] > key)
           {
               right = mid-1;
           }
           else if(arr[mid] < key)
           {
               left = mid+1;
           }
       }
       return -1;
   }

   int main()
   {
       int n,key;
       int arr[11] = {0, 5, 14, 17, 22, 31, 55, 68, 72, 81, 88};
       n = sizeof(arr)/sizeof(arr[0]);
       printf("Nhap so can tim: ");
       scanf("%d", &key);
       int t = binarySearch(arr, n, key);
       if(t == -1){
           printf("Khong ton tai trong mang!");
       }else{
           printf("%d xuat hien tai vi tri %d", key, t+1);
       }
       return 0;
   }

 

Và đây là kết quả sau khi chạy chương trình!

  Nhap so can tim: 55
  55 xuat hien tai vi tri 6

 

Bằng cách áp dụng thuật toán tìm kiếm nhị phân, độ phức tạp cho trường hợp xấu nhất là O(log(n)).

Các bạn có thể copy code, chạy thử sau đó phân tích và cảm nhận nhé. Vì học phải đi đôi với hành, nếu chỉ đọc lý thuyết mà không thực hành thì rất khó để hiểu và nhớ kiến thức đúng không nào!

Kết luận

Vừa rồi chúng ta đã cùng tìm hiểu về thuật toán Tìm kiếm Nhị Phân (Binary Search) và các bước hoạt động của nó.

Qua bài viết này mình cũng mong các bạn có thể hiểu và áp dụng được nó vào các bài thuật toán hay các project khác nhé. Hẹn gặp các bạn ở bài viết tiếp theo!

 

Nguyễn Thế Lập - CTV