Đọ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