Tìm kiếm nhị phân

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong khoa học máy tính, thuật toán tìm kiếm nhị phân là một thuật toán dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp. Thuật toán hoạt động như sau. Trong mỗi bước, so sánh phần tử cần tìm với phần tử nằm ở chính giữa danh sách. Nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc. Nếu chúng không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách. Vì số lượng phần tử trong danh sách cần xem xét giảm đi một nửa sau mỗi bước, nên thời gian thực thi của thuật toán là hàm lôgarit.

Tổng quan[sửa | sửa mã nguồn]

Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó.

Thuật toán tìm kiếm nhị phân chạy nhanh hơn tìm kiếm tuyến tính nhưng cũng có một số nhược điểm. Tìm kiếm nhị phân có thể chậm hơn bảng băm. Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân. Thao tác này thường tốn nhiều thời gian.

Lập trình[sửa | sửa mã nguồn]

Sau đây là mã giả của thuật toán tìm kiếm nhị phân.

   "int"  BinarySearch  (Array a, int x)  {
   int left = 0, right, mid;  right = a.n - 1;
   while (left <= right)    {
       mid = (left + right)/2;  
       if (a.A[mid] > x)  right = mid - 1;
       else  left = mid + 1;   
   };  
   if (left == 0) 
       printf ("Ko tim thay phan tu %d \n", x);
   return left;

}

Thời gian thực thi[sửa | sửa mã nguồn]

Sau mỗi phép so sánh, số lượng phần tử trong danh sách cần xét giảm đi một nửa. Thuật toán kết thúc khi số lượng phần tử còn không quá 1. Vì vậy thời gian thực thi của thuật toán là O(\log n).

Mở rộng[sửa | sửa mã nguồn]

Trong trường hợp cần tìm một phần tử trong nhiều danh sách cùng một lúc, có thể sử dụng phương pháp "đổ xuống một phần" (tiếng Anh fractional cascading) để tăng tốc các phép tìm kiếm sau phép tìm kiếm thứ nhất.[1][2]

Ngay cả trường hợp phép so sánh có nhiễu, có những thuật toán mở rộng để giải quyết cùng bài toán như thuật toán tìm kiếm nhị phân.[3]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Chazelle, Bernard; Guibas, Leonidas J. (1986), “Fractional cascading: I. A data structuring technique”, Algorithmica 1 (1): 133–162, doi:10.1007/BF01840440 
  2. ^ Chazelle, Bernard; Guibas, Leonidas J. (1986), “Fractional cascading: II. Applications”, Algorithmica 1 (1): 163–191, doi:10.1007/BF01840441 
  3. ^ Karp, Richard M.; Kleinberg, Robert (2007), “Noisy binary search and its applications”, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '07, New Orleans, Louisiana: Society for Industrial and Applied Mathematics, tr. 881––890, ISBN 978-0-898716-24-5  Đã bỏ qua tham số không rõ |acmid= (trợ giúp); Đã bỏ qua tham số không rõ |numpages= (trợ giúp); Đã bỏ qua tham số không rõ |address= (trợ giúp)