Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán được sử dụng rất nhiều trong lập trình lập trình: tìm kiếm nhị phân. Hãy cùng xem thuật toán này có gì thú vị nhé!

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong C++
• Các kiến thức cần thiết để theo dõi khóa học
• Con trỏ trong C++
• Sắp xếp

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Tổng quan về tìm kiếm nhị phân
• Một số hàm tìm kiếm nhị phân trong C++

Bài toán đặt ra

Cho một dãy số gồm n số nguyên dươngai [n≤106, ai≤109]. Cóq truy vấn[q ≤ 106], mỗi truy vấn gồm một số nguyên dươngx, nếux có trong dãy a thì in ra “YES”, còn không thì in ra “NO”.

Ví dụ:

_Howkteam_com.png]

Lời giải ban đầu

Giải thích: Trong ví dụ trên có 5 truy vấn là 3, 4, 8, 9, 1 với kết quả lần lượt là YES, NO, YES, YES, NO với ý nghĩa như đã nêu ở đề bài.

Với suy nghĩ thông thường, để có thể kiểm tra được 1 phần tử có trong dãy hay không, ta sẽ duyệt qua toàn bộ dãy. Nếu như gặp một phần tử giống với giá trị đang tìm kiếm, ta sẽ in ra “YES”, còn nếu tìm cả dãy mà không thấy, ta sẽ in ra “NO”.

Từ suy nghĩ trên, ta sẽ code như sau:

`

include

using namespace std; const int MaxN = 1 + 1e6; int n, a[MaxN], q; int main[]{

freopen["CTDL.inp","r",stdin];  
freopen["CTDL.out","w",stdout];  
cin >> n;  
for[int i = 0 ; i < n ; ++i] cin >> a[i];  
cin >> q;  
while[q--]{  
    int x, check = 0;  
    cin >> x;  
    for[int i = 0 ; i < n ; ++i]  
    if[a[i] == x]{  
        check = 1;  
        break;  
    }  
    if[check] cout > q;  
while[q--]{  
    int x;  
    cin >> x;  
    if[binary_search[a, n, x]] cout  a[i];  
sort[a, a + n];  
cin >> q;  
while[q--]{  
    int x;  
    cin >> x;  
    if[binary_search[a, a + n, x]] cout