Đọc phần 1 tìm kiếm nhị phân ở đây.

Bài toán 2: Cho dãy gồm ~n~ số nguyên ~A_1, A_2,..,A_n~ là dãy không giảm và số nguyên ~X~. Tìm vị trí xuất hiện đầu tiên của số ~X~ trong dãy đã cho.

Đây là bài toán mở rộng của bài toán 1, điểm khác nhau là dãy số này có thể có các số bằng nhau, tức là vào thời điểm ~A_m = X~ thì ~m~ chưa chắc đã là đáp án cần tìm như ví dụ hình dưới:

Giải pháp đơn giản là ta lưu lại vị trí ~m~ vừa tìm được nhưng không dừng vòng lặp mà tiếp tục tìm kiếm. Cần tìm vị trí nhỏ nhất nên rất có thể đáp án sẽ là một số còn ~< m~, do vậy ta sẽ tiếp tục tìm kiếm trong phạm vi bên trái đoạn ~[l, r]~, tức là cho ~r = m-1~.

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

Bài toán 3: Cho dãy gồm ~n~ số nguyên ~A_1, A_2,..,A_n~ là dãy không giảm và số nguyên ~X~. Tìm vị trí xuất hiện cuối cùng của số ~X~ trong dãy đã cho.

Bài toán này tương tự bài số 2, cần tìm vị trí lớn nhất nên ta tiếp tục cho tìm kiếm nhị phân ở đoạn bên phải của ~[l, r]~, tức là cho ~l = m+1~.

Bài cơ bản 3 tại đây: https://thaynamlamson.com/problem/tknp3

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