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

1. Giải thuật

Đối với những dãy số đã có thứ tự (giả sử thứ tự tăng), các phần tử trong dãy có quan hệ a(i-1) <= a(i) <= a(i+1), từ đó kết luận được nếu x>a(i) thì x chỉ có thể xuất hiện trong đoạn [a(i+1),a(n)] của dãy, ngược lại nếu x<a(i) thì x chỉ có thể xuất hiện trong đoạn [a(i),a(i-1)] của dãy. Giải thuật tìm kiếm nhị phân áp dụng nhận xét trên đây để tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần ưử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nữa trên hay nữa dưới của dãy tìm kiếm hiện hành. Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử a(left)....a(right), các bước tiến hành như sau:

Bước 1: left=1; right = N; // tìm kiếm trên tất cả các phần tử

Bước 2: mid = (left+right)/2;//lấy mốc so sánh
So sánh a[mid] với x, có 3 khả năng:
+ a[mid] = x: Tìm thấy. Dừng lại.
+ a[mid]>x: // tìm tiếp x trong dãy con a(left)...a(mid-1):
right = mid-1;
+ a[mid]<x: //tìm tiếp x trong dãy a(mid+1)...a(right):
left = mid+1;
Bước 3: Nếu left<=right //còn phần tử chưa xét=>tìm tiếp
Lặp lại Bước 2
Ngược lại: Dừng;//Đã xét hết phần từ

2. Cài đặt
Thuật toán tìm nhị phân có thể được cài đặt thành hàm BinarySearch:

Mã ngôn ngữ C

CODE:: int BinarySearch(int a[], int N, int x){ int left = 0, right = N - 1; int mid; do { mid = (left + right) / 2; if (x == a[mid]) return mid;//Thấy x tại mid else if (x < a[mid]) right = mid - 1; else left = mid + 1; } while (left <= right); return -1;// tìm hết dãy mà không có x}

3. Đánh giá giải thuật
Trường hợp tìm kiếm nhị phân, có bảng phân tích sau:

Vậy giải thuật tìm kiếm nhị phân có độ pưức tạp tính toán cấp n:
T(n) = O(log(2)N).

4.Nhận xét

*Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho các dãy đã có thứ tự.

*Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm kiếm tuyến tính do T(nhị phân)(n) = O(log(2)N) < T(tuyến tính)(n) = O(n).

*Tuy nhiên khi muốn áp dụng giải thuật tìm kiếm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số đã có thứ tự. Thời gian này không nhỏ, và khi dãy có biến động cần phải tiến hành sắp xếp lại...Tất cả các nhu cầu đó tạo ra khuyết điểm chính cho giải thuật tìm kiếm nhị phân. Ta cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất.

[LinearSearch] Thuật toán tìm kiếm tuyến tính
[Demo đồ họa] Thuật toán tìm kiếm
[Demo đồ họa] Thuật toán sắp xếp