Tổng quan về tìm kiếm nhị phân

Trong bài học kinh nghiệm ngày thời điểm ngày hôm nay, tất cả chúng ta sẽ cùng nhau đi tìm hiểu và khám phá 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ì mê hoặc nhé !

Nội dung

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

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

Bạn đang đọc: Tổng quan về tìm kiếm nhị phân | How Kteam

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ương ai ( n ≤ 106, ai ≤ 109 ). Có q truy vấn ( q ≤ 106 ), mỗi truy vấn gồm một số ít nguyên dương x, nếu x có trong dãy a thì in ra “ YES ”, còn không thì in ra “ NO ” .
Ví dụ :

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 hiệu quả lần lượt là YES, NO, YES, YES, NO với ý nghĩa như đã nêu ở đề bài .
Với tâm lý thường thì, để hoàn toàn có thể kiểm tra được 1 thành phần có trong dãy hay không, ta sẽ duyệt qua hàng loạt dãy. Nếu như gặp một thành phần 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ừ tâm lý 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 << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

Hãy cùng nhìn nhận độ phức tạp của thuật toán trên. Ta nhận thấy có một vòng lặp n lần nằm trong một vòng lặp q lần nên độ phức tạp của thuật toán là O ( n × q ). Vậy liệu có cách nào giảm độ phức tạp của thuật toán tìm kiếm xuống không ?

Ý tưởng

Giả sử dãy số ở trong ví dụ của tất cả chúng ta được sắp xếp không giảm. Khi đó ta có a = [ 2, 2, 3, 5, 7, 8, 9 ]. Ta cần kiểm tra x = 3 liệu có thuộc dãy a hay không. Vậy thì ta sẽ làm như thế nào ?
Hãy xét vị trí i = 4 trong dãy a ( ai = 7 ). Khi này, ta chia dãy làm hai phần : những số nhỏ hơn 7 ( màu xanh ) và những số lớn hơn hoặc bằng 7 ( màu vàng ) .

Ta nhận thấy 3 nhỏ hơn 7, do đó số 3 không hề nằm trong phần màu vàng mà chỉ hoàn toàn có thể nằm trong phần màu xanh. Do đó, khi liên tục tìm kiếm, ta chỉ tìm kiếm trên vùng màu xanh. Việc này giúp ta giảm bớt những bước tìm kiếm .

Lời giải cải tiến

Từ ý tưởng sáng tạo được đưa ra ở trên, ta hoàn toàn có thể đưa ra một lời giải như sau :

Chọn một thành phần trong đoạn cần xét
So sánh thành phần cần tìm kiếm với thành phần được chọn :
- Nếu thành phần cần tìm kiếm nhỏ thành phần được chọn ta sẽ liên tục tìm kiếm trong đoạn nhỏ hơn
- Nếu thành phần cần tìm kiếm lớn thành phần được chọn ta sẽ liên tục tìm kiếm trong đoạn lớn hơn

Đây chính là cơ sở của thuật toán tìm kiếm nhị phân. Để tìm hiểu và khám phá cụ thể hơn, ta sẽ cùng đến với phần tiếp theo của bài học kinh nghiệm ngày thời điểm ngày hôm nay .

Tổng quan về tìm kiếm nhị phân

Khái niệm và ý tưởng

Tìm kiếm nhị phân là một thuật toán tìm kiếm giá trị xác lập trên dãy đã sắp xếp .
Thuật toán hoạt động giải trí bằng cách chọn thành phần trung vị ( thành phần ở vị trí chính giữa ). Nếu thành phần cần tìm khác thành phần trung vị ta sẽ liên tục xét. Nếu thành phần cần tìm kiếm nhỏ hơn thành phần trung vị, ta sẽ liên tục tìm kiếm trên nửa nhỏ hơn, ngược lại ta sẽ tìm kiếm trên nửa lớn hơn. Kết thúc quy trình tìm kiếm mà không có thành phần nào bằng thành phần cần tìm, ta sẽ Tóm lại thành phần cần tìm không có trong dãy .

Code

#include
using namespace std;

const int MaxN = 1 + 1e6;

int n, a[MaxN], q;

bool binary_search(int a[], int sz, int target){
    int low = 0, high = sz - 1;
    while(low <= high){
        int tg = (low + high) / 2;
        if(a[tg] == target) return 1;
        if(target < a[tg]) high = tg - 1;
        else low = tg + 1;
    }
    return 0;
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    sort(a, a + n);
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        if(binary_search(a, n, x)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

Mình sẽ có 1 số ít quan tâm cho những bạn về đoạn code trên như sau :

Do tìm kiếm nhị phân chỉ hoạt động giải trí trên dãy đã sắp xếp nên những bạn sẽ cần dùng hàmsortđể sắp xếp dãy trước khi dùng tìm kiếm nhị phân .
Do khoảng tìm kiếm luôn là một đoạn liên tục các giá trị nguyên, ta không cần lưu tất cả phần tử của đoạn khi tìm kiếm mà chỉ cần duy trì hai biến
low và high tượng trưng cho phần tử đầu và cuối của đoạn.
Ta hoàn toàn có thể tối ưu thuật toán hơn bằng việc dừng sớm nếu trong quy trình so sánh gặp một thành phần trung vị thỏa nhu yếu đề bài chứ không cần đợi đến khi đoạn tìm kiếm chỉ còn một thành phần .

Vậy đơn cử đoạn code trên sẽ chạy thế nào ?
Hãy giả sử ta đang cần tìm kiếm thành phần x = 3 trong dãy ở ví dụ. Khi đó, quy trình tìm kiếm sẽ như sau :

Độ phức tạp của thuật toán

Ta thấy, ở mỗi bước, khoảng tìm kiếm sẽ bị giảm đi một nửa nên chi phí cho việc tìm kiếm một phần tử sẽ là
O(logn). Do đó, độ phức tạp của toàn bộ chương trình trên sẽ là
O(n×logn).

Một số hàm tìm kiếm nhị phân trong C++

Trong C + + có 1 số ít hàm vận dụng tư tưởng của tìm kiếm nhị phân như binary_search, lower_bound, upper_bound .

Khai báo

Thông thường để thêm những hàm trên vào chương trình, tất cả chúng ta sẽ thêm thư viện như sau :

#include

Tuy nhiên, ở trong suốt khóa học này mình sẽ sử dụng header sau :

#include

Xem thêm: Laravel là gì? Tại sao Laravel là PHP Framework tốt nhất năm 2021?

Header này sẽ giúp tất cả chúng ta thêm tổng thể những thư viện về thuật toán mà tất cả chúng ta sẽ sử dụng trong khóa học này .

Sử dụng

Hàm binary_search

Hàm binary_search sẽ được sử dụng như sau :

binary_search ( { first }, { last }, { element } ) ;

Trong đó :

first, last lần lượt là 2 con trỏ trỏ đến vị trí xuất phát và kết thúc của dãy cần tìm kiếm. Khoảng được tìm kiếm là [ first, last ), tức là tổng thể những thành phần giữa first và last và thêm thành phần được trỏ bởi first nhưng không có thành phần trỏ bởi last
element: thành phần cần tìm kiếm
Hàm sẽ trả về giá trịbool,truenếu sống sót thành phần element trong đoạn cần xét ,false
nếu thành phần element không nằm trong đoạn cần xét

Hàm binary_search sẽ được vận dụng vào bài toán khởi đầu của ta 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];
    sort(a, a + n);
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        if(binary_search(a, a + n, x)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

Hàm lower_bound

Hàm lower_bound sẽ được sử dụng như sau :

lower_bound ( { first }, { last }, { element } ) ;

Trong đó :

first, last lần lượt là 2 con trỏ trỏ đến vị trí xuất phát và kết thúc của dãy cần tìm kiếm. Khoảng được tìm kiếm là [ first, last ), tức là tổng thể những thành phần giữa first và last và thêm thành phần được trỏ bởi first nhưng không có thành phần trỏ bởi last
element: thành phần cần tìm kiếm
Hàm sẽ trả về con trỏ trỏ đến thành phần tiên phong trong đoạn đang xét không nhỏ hơn thành phần element

Mình có đoạn code minh hoạ cách dùng lower_bound như sau :

#include
using namespace std;

const int MaxN = 1 + 1e6;

int main(){
    int a[] = {4, 2, 4, 9, 6, 1, 10};
    sort(a, a + 7);
    // Khi này dãy a là: 1 2 4 4 6 9 10
    auto pos = lower_bound(a, a + 7, 4);
    cout << "Vi tri dau tien khong nho hon 4 la " << pos - a << endl;
    // Kết quả là 2 (do a[2] == 4)

    return 0;
}

Hàm upper_bound

Cách sử dụng hàm upper_bound trọn vẹn tương tự như hàm lower_bound, chỉ khác là upper_bound sẽ tìm thành phần tiên phong lớn hơn thành phần element .
Mình có đoạn code minh hoạ cách dùng upper_bound như sau :

#include
using namespace std;

const int MaxN = 1 + 1e6;

int main(){
    int a[] = {4, 2, 4, 9, 6, 1, 10};
    sort(a, a + 7);
    // Khi này dãy a là: 1 2 4 4 6 9 10
    auto pos = upper_bound(a, a + 7, 4);
    cout << "Vi tri dau tien lon hon 4 la " << pos - a << endl;
    // Kết quả là 4 (do a[4] == 6)

    return 0;
}

Độ phức tạp

Tất cả các hàm mình vừa nêu ở trên đều mất độ phức tạp
O(logn).

Vấn đề bài sau

Từ những kỹ năng và kiến thức về tìm kiếm nhị phân, những bạn hãy thử tâm lý bài toán sau :

Có một phân xưởng gồm n máy
(n ≤ 105), máy thứ i cần chính xác
ai ngày
(0 < ai ≤ 109) để hoàn thành 1 sản phẩm như nhau. Hãy tính thời gian ít nhất để có thể hoàn thành tối thiểu k sản phẩm
(0< k≤ 109).

Ví dụ

Để biết cách làm là gì thì hãy cùng chờ đến bài học kinh nghiệm tiếp theo nhé !

Giải thích: Trong vòng 10 ngày, máy 1 làm được 3 sản phẩm, máy 2 làm được 5 sản phẩm, máy 3 làm được 1 sản phẩm, tổng cộng là 9 sản phẩm như yêu cầu đề bài.

Kết luận

Qua bài này chúng ta đã nắm được các kiến thức ban đầu về
Tìm kiếm nhị phân

Bài sau chúng ta sẽ tiếp tục tìm hiểu về
Ứng dụng của tìm kiếm nhị phân

Xem thêm: Tìm hiểu Event trong Laravel – Blog Văn Long

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

Thảo luận

Nếu bạn có bất kể khó khăn vất vả hay vướng mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI và ĐÁP trên thư viện Howkteam. com để nhận được sự tương hỗ từ hội đồng .

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com