Ứng dụng của tìm kiếm nhị phân

Trong bài học ngày hôm trước, chúng ta đã cùng nhau đi tìm hiểu về tìm kiếm nhị phân. Ngày hôm nay, chúng ta sẽ tiếp tục tìm hiểu về ứng dụng của thuật toán này trong các bài toán khác.

---

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   
• 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ề:

• Ứng dụng của tìm kiếm nhị phân
• Nhận biết sử dụng tìm kiếm nhị phân

---

Bài toán đặt ra

Ở trong bài học trước, mình đã nêu ra cho các bạn một bài toán. Bây giờ, mình sẽ trình bày lại đề bài:

Có một phân xưởng gồm  máy , máy thứ i cần chính xác  ngày  để 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  sản phẩm .

Ví dụ

Input	Output
3 9 3 2 7	10

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.

Đã có bạn nào tìm ra được cách giải của riêng mình chưa? Nếu rồi thì hãy xem cách giải của mình có giống với các bạn không nhé còn nếu các bạn chưa tìm ra cách giải thì hãy xem mình sẽ giải quyết bài toán này như thế nào nhé!

---

Lời giải ban đầu

Cách giải đơn giản nhất khi nhìn vào bài toán này chính là thử. Ta sẽ thử số lượng ngày cần để hoàn thành  sản phẩm. Nếu đủ để tạo ra  sản phẩm ta sẽ ghi nhận kết quả, nếu không thì ta sẽ tăng số lượng ngày cần để hoàn thành và tiếp tục thử.

Từ suy nghĩ trên, ta có code như sau:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MaxN = 1 + 1e6;

int n, k, a[MaxN];

bool check(ll days){
    ll products = 0;
    for(int i = 0 ; i < n ; ++i) products += days / a[i];
    return products >= k;
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    ll res = 0;
    while(!check(res)) res++;
    cout << res << endl;

    return 0;
}

Tuy nhiên, hẳn các bạn cũng nhận ra là cách làm này sẽ rất chậm. Giả sử   thì khi đó kết quả là  hay có nghĩa là vòng lặp của chúng ta sẽ lặp  lần. Vậy thì có cách làm nào nhanh hơn không?

---

Nhận xét

Ta thấy, bài toán này sẽ có một tính chất đặc biệt sau: Nếu như ngày thứ  ta không hoàn thành được  sản phẩm thì từ ngày 1 đến ngày  ta cũng không hoàn thành được  sản phẩm. Tính chất này sẽ giúp chúng ta giải quyết bài toán như thế nào đây?

Giả sử ta đang cần tìm kiếm thời gian ngắn nhất trong đoạn  và ta đã biết chắc chắn đến ngày  sẽ hoàn thành được ít nhất  sản phẩm.

Ta sẽ chọn một ngày  nào đó sao cho . Nếu như đến ngày  mà ta cũng không thể hoàn thành đủ  sản phẩm thì theo nhận xét bên trên, xét từ ngày  đến ngày  là không cần thiết và ta sẽ tiếp tục tìm kiếm kết quả trong đoạn . 

Còn nếu đến ngày  mà ta hoàn thành tối thiểu  sản phẩm thì ta sẽ tìm kết quả trong đoạn  do lúc này ta biết ta sẽ cần nhiều nhất  ngày để hoàn thành  sản phẩm.

Đọc ý tưởng trên các bạn có thấy quen thuộc không? Đó chính là tư tưởng của tìm kiếm nhị phân. Cụ thể áp dụng vào lời giải như thế nào thì hãy cùng tìm hiểu tiếp nhé.

---

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

Từ những nhận xét trên ta sẽ rút ra được lời giải như sau:

• Tìm kiếm kết quả trên đoạn  mà ta biết chắc chắn tại ngày  sẽ hoàn thành
• Lấy giá trị trung bình  của đoạn
• Kiểm tra giá trị trung bình . Nếu giá trị đó thỏa mãn ta sẽ tiếp tục tìm kiếm trên đoạn  còn ngược lại, ta sẽ tìm kiếm trên đoạn .
• Quá trình kết thúc khi đoạn tìm kiếm chỉ chứa 1 phần tử duy nhất

Vậy cụ thể ta sẽ triển khai lời giải trên như thế nào?

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MaxN = 1 + 1e6;

int n, k, a[MaxN];

bool check(ll days){
    ll products = 0;
    for(int i = 0 ; i < n ; ++i) products += days / a[i];
    return products >= k;
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    ll l = 0, r = 1e18;
    while(l < r){
        ll tg = (l + r) / 2;
        if(check(tg)) r = tg;
        else l = tg + 1;
    }
    cout << l << endl;

    return 0;
}

Mình sẽ giải thích một chi tiết mà các bạn có thể cảm thấy khó hiểu ở đoạn code trên, đó là phép gán . Tại sao lại có con số  ở đây? Như mình đã nói ở trên, khi ta xét đoạn thì ta phải đảm bảo  chính xác. Có nghĩa là trong trường hợp xấu nhất thì  vẫn phải đúng. Vậy trường hợp xấu nhất của ta là gì? Đó chính là khi , kết quả khi này là . Đó chính là lí do mình thực hiện phép gán trên.

Vậy thì độ phức tạp của chương trình trên sẽ là bao nhiêu. Do qua mỗi vòng while, phạm vi tìm kiếm nhỏ đi một nửa và mỗi lần kiểm tra mất  nên độ phức tạp của toàn bộ chương trình là .

---

Nhận biết sử dụng tìm kiếm nhị phân

Vậy thì làm sao chúng ta có thể nhận biết được khi nào nên sử dụng tìm kiếm nhị phân hay dạng bài toán nào có thể áp dụng chúng?

Giả sử ta có một hàm  trả về bool cho biết giá trị  ta đang xét có hợp lí hay không, đoạn đang được xét là , kết quả bài toán là  thì bài toán có thể áp dụng tìm kiếm nhị phân khi và chỉ khi.

Nói một cách dễ hiểu hơn thì đoạn ta đang xét phải có 1 trong 2 dạng sau:

Hoặc

---

Lưu ý khi sử dụng tìm kiếm nhị phân

Trong bài toán ví dụ của mình ở trên, ta đang đi tìm kết quả nhỏ nhất có thể. Thế nhưng, sẽ hơi khác một chút khi ta phải đi xét kết quả lớn nhất có thể. Sự khác biệt ở đây là gì?

Hãy giả sử chúng ta đang xét đoạn . Cả hai giá trị này đều hợp lí, khi đó thì ta sẽ chọn  do ta cần kết quả lớn nhất có thể. Tuy nhiên, hãy chú ý vào cách vòng while ở đoạn code mà mình viết chạy:

while(l < r){
    ll tg = (l + r) / 2;
    if(check(tg)) r = tg;
    else l = tg + 1;
}

Khi này, hay . Do  là kết quả hợp lý nên khi này check(tg) trả về true dẫn đến  hay có nghĩa là  nên kết quả thu được là  thay vì . Do đó, nếu cần tìm kết quả lớn nhất, ta phải sửa lại như sau:

while(l < r){
    ll tg = (l + r + 1) / 2;
    if(check(tg)) l = tg;
    else r = tg - 1;
}

Điều này còn có nghĩa là khi cần tìm kết quả nhỏ nhất thì ta ưu tiên xét giá trị nhỏ hơn trước còn khi cần tìm giá trị lớn nhất ta sẽ cần ưu tiên xét giá trị lớn hơn trước.

Nói điều này ở đây có thể các bạn sẽ chưa thể hiểu ngay được. Tuy nhiên, hãy thử làm một số bài toán về tìm kiếm nhị phân mà cần tìm kết quả lớn nhất. Khi đó, các bạn sẽ hiểu được vấn đề mà mình đã trình bày ở đây.

---

Kết luận

• Qua bài này chúng ta đã nắm được về Tìm kiếm nhị phân
• Bài sau chúng ta sẽ tìm hiểu về Hai con trỏ
• 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 hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.