Bài toán: Cho dãy ~A_1, A_2,..,A_n~ là dãy không giảm gồm ~n~ số nguyên khác nhau và số nguyên ~X~. Hỏi trong dãy đã cho có phần tử nào có giá trị bằng ~X~ không?

Một cách ngây thơ (ta hay gọi là code trâu) là duyệt tuần tự từng phần tử của dãy ~A~ rồi kiểm tra xem có số nào bằng ~X~ không, cách này dành cho người mới học, đơn giản như sau:

 for (int i=1;i<=n;i++)
    if (A[i]==X){
        cout<<i;
        return 0;
    }

Cách làm trên, sau mỗi lần so sánh ~A[i]~ với ~X~, nếu may mắn ta gặp được vị trí cần tìm hoặc không thì sẽ chỉ loại được một vị trí không đúng đáp án, có nghĩa là trường hợp xấu nhất (không có đáp án hay đáp án là số cuối cùng trong dãy số) thì ta phải so sánh ~n~ lần.

Đối với dãy số đã được sắp xếp (ở bài này là không giảm) ta có cách tìm kiếm nhị phân như sau:

Duy trì 2 giá trị ~l, r~ với ý nghĩa: số ~X~ nếu có trong dãy số thì nó chỉ nằm trong phạm vi từ ~A_l~ đến ~A_r~ hay nói cách khác: phạm vi bên ngoài từ ~A_l~ đến ~A_r~ chắc chắn không có số ~X~. Xét ví dụ sau với dãy ~A =[3, 5, 6, 8, 9, 10, 12, 14, 15]~, ~X = 10~.

Thay vì lần lượt so sánh lần lượt các số trong dãy ~A~ với ~X~, ta lấy phần tử ở giữa ~l~ và ~r~ (gọi là ~m = (l+r)/2~), so sánh ~A_m~ với ~X~. Khi đó:

• Nếu ~A_m = X~: Đã tìm được đáp án là ~m~.
• Nếu ~A_m < X~: Nếu tồn tại ~X~ trong dãy ~A~ thì ~X~ chỉ có thể nằm trong phạm vi từ ~A_{m+1}~ đến ~A_r~, hay nói cách khác, toàn bộ các số ~A_l~ đến ~A_m~ đều nhỏ hơn ~X~ nên sẽ bị loại bỏ khỏi phạm vi tìm kiếm, ta cho ~l~ di chuyển lên ~m+1~, tức là sau lần so sánh này phạm vi tìm kiếm sẽ từ ~m+1~ đến ~r~.
• Nếu ~A_m > X~: Lập luận tương tự như trên, trường hợp này sẽ loại bỏ toàn bộ các số từ ~A_m~ đến ~A_r~, ta cho ~r = m-1~.

Quá trình trên được lặp đi lặp lại cho đến khi gặp được kết quả hoặc phạm vi tìm kiếm không còn (tức là ~l~ không còn ~\le r~).

    l = 1, r = n;
    while (l<=r)
    {
        m = (l+r)/2;
        if (A[m]==X) {
            ans = m; break;
        }
        if (A[m]<X) l = m+1;
        if (A[m]>X) r = m-1;
    }

Mỗi lần so sánh ~A_m~ với ~X~ cho ta hoặc là tìm được đáp số, hoặc là phạm vi tìm kiếm được giảm 1 nửa, do đó số lần lặp của vòng lặp trên chỉ tối đa là log(n), hiểu nôm na là nếu ~n = 10^6~ thì số lần lặp chỉ khoảng 20.

Các em học sinh có thể thực hành bài cơ bản tại đây: https://thaynamlamson.com/problem/tknp1