Ý tưởng
Đối với những dãy số đã có thứ tự (tăng dần), các phần tử đã có quan hệ ai-1 ≤ ai ≤ ai+1. Nếu x > ai thì x chỉ có thể xuất hiện trong đoạn [ai+1, aN], ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1, ai-1].
Giải thuật áp dụng nhận xét trên để 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ại mỗi bước, so sánh x với phần tử nằm giữa dãy tìm kiếm hiện hành, dựa vào kết quả so sánh để quyết định giới hạn của 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 hiện hành.
Giải thuật
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
+ a[mid] = x: Tìm thấy. Dừng.
+ a[mid] > x: Tìm tiếp x trong dãy con aleft..amid-1
right = mid – 1;
+ a[mid] < x: Tìm tiếp x trong dãy con amid+1..aright
left = mid + 1;
Bước 3: Nếu left ≤ right Lặp lại bước 2. // còn phần tử chưa xét
Ngược lại: Dừng