Thuật toán tìm kiếm nhị phân

Đăng bởi Admin

Tháng 10 6, 2022

Trong khoa học máy tính, tìm kiếm nhị phân binary search), còn gọi là tìm kiếm nửa khoảng (half-interval search), tìm kiếm logarit (logarithmic search), hay chặt nhị phân (binary chop), là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã có thứ tự hay đã được sắp xếp. Thuật toán tiến hành chia đôi không gian tìm kiếm sau mỗi lần lặp, sau đó xét tiếp trong nửa khoảng mà có khả năng chứa giá trị cần tìm, cứ như vậy cho đến khi không chia đôi được nữa.

Hay nói cách khác thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng. Nếu không phải giá trị cần tìm, phần nửa mảng không chứa giá trị cần tìm sẽ bị bỏ qua và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa và so sánh với giá trị cần tìm, cứ thế lặp lại cho đến khi tìm thấy giá trị đó. Nếu phép tìm kiếm kết thúc khi nửa còn lại trống thì giá trị cần tìm không có trong mảng.

Giả sử dãy đã được sắp xếp tăng dần, giải thuật tìm kiếm nhị phân được thực hiên như sau:

– Giả sử cần tìm kiếm trong đoạn $a[l \ldots r]$ với giá trị tìm kiếm là $k$ , trước hết ta xét phần tử nằm ở giữa dãy là $a_{m i d}$ với $m i d=\left\lfloor\frac{l+r}{2}\right\rfloor$ .
– Nếu $a_{\text {mid }}<k$ thì nghĩa là đoạn từ $a_l$ tới $a_{\text {mid }}$ chỉ chứa toàn các đối tượng có giá trị nhỏ hơn $k$ , nên ta tiếp tục quá trình tìm kiếm trên đoạn từ $a_{m i d+1}$ tới $a_n$ .
– Nếu $a_{\text {mid }}>k$ thì nghĩa là đoạn từ $a_{\text {mid }}$ tới $a_r$ chỉ chứa toàn các đối tượng có giá trị lớn hơn $k$ , nên ta tiếp tục quá trình tìm kiếm trên đoạn từ $a_1$ tới $a_{\text {mid }-1}$ .
– Nếu $a_{\text {mid }}=k$ thì quá trình tìm kiếm thành công.
Quá trình tìm kiếm sẽ thất bại nếu như đến một bước nào đó, tập tìm kiếm bị rỗng $(l > r)$ .

binary_search(a, k)
{
    sort(a);
    l = 1, r = n;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (a[mid] == k)
            return mid;

        if (a[mid] < k)
            l = mid + 1;
        else 
            r = mid - 1;
    }
    return -1;
}

Ví dụ như bạn có một dãy số tăng từ 1 đến 100, yêu cầu bạn tìm số 30. Bạn xem phần tử chính giữa của dãy số thì thấy là số 50, vậy thì bạn biết chắc là 30 chỉ có thể nằm trong khoảng dưới 50 thôi, vậy thì giới hạn tìm kiếm được thu hẹp lại một nửa. Ví dụ như tìm số 70 chẳng hạn thì 50 lại nhỏ hơn 70, do đó ta biết chắc 70 chỉ có thể nằm trong khoảng từ 51 đến 100 thôi. Cứ tiếp tục như thế cho đến khi tìm gặp hoặc không thể chia đôi khoảng nữa.

Tìm kiếm nhị phân chạy theo thời gian logarit trong trường hợp tệ nhất, thực hiện $O(\log n)$ bước so sánh. Thuật toán tìm kiếm nhị phân nhanh hơn so với tìm kiếm tuyến tính (tìm kiếm tuần tự), ngoại trừ các trường hợp mảng có kích thước nhỏ. Tuy nhiên, mảng phải được sắp xếp trước khi áp dụng tìm kiếm nhị phân.

Ví dụ:

Cho một dãy số $\mathrm{A}$ gồn $\mathrm{N}$ số nguyên dãy được sắp xếp tăng dần và $\mathrm{Q}$ truy vấn, mỗi truy vấn là một số nguyên $X$ . Với mỗi truy vấn hãy tìm vị trí xuất hiện của $X$ trong $A$ ? Nếu không tồn tại giá trị $\mathrm{X}$ trong $\mathrm{A}$ , in ra $-1$ .

Thuật toán:

Do dãy có thứ tự tăng dần nên có thể áp dụng thuật toán tìm kiếm nhị phân để có thể tìm được vị trí xuất hiện của số nguyên X trong từng truy vấn.

Chương trình:

#include<bits/stdc++.h>
using namespace std;
int q, n, arr[500016], x;
int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 1; i <= q; i++)
    {
        cin >> x;
        int l = 1, r = n;
        bool check = false;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (arr[mid] == x)
            {
                cout << mid << endl;
                check = true;
                break;
            }
            if (arr[mid] < x)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        if (check == false)
        {
            cout << -1 << endl;
        }
    }
}

Chia sẻ: