---
title
Tìm kiếm nhị phân - Bài tập và lời giải
---

Tìm kiếm nhị phân - Bài tập và lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Tổng quan
Ở bài viết trước, chúng mình đã giới thiệu đến bạn giải thuật Tìm kiếm nhị phân, một thuật toán tìm kiếm hoạt động dựa trên tính có thứ tự của dãy cho trước. Khi tiếp cận một thuật toán, bên cạnh việc nắm vững kiến thức căn bản thì kĩ năng áp dụng lý thuyết vào thực hành là rất quan trọng. Trong phần này là một số bài toán mà bạn có thể ứng dụng Tìm kiếm nhị phân để giải quyết.
# Bài tập
## Bài 1: [CSES - Concert Tickets](https://cses.fi/problemset/task/1091/)
#### Tóm tắt
- Có $n$ vé đi xem concert ca nhạc có sẵn, mỗi vé có $1$ giá bán nhất định. Sau đó có $m$ người khách hàng đến mua vé, lần lượt từng người một. Mỗi người ra giá cao nhất mà họ có thể mua, sau đó họ sẽ nhận được một vé có giá lớn nhất sao cho không vượt quá giá tối đa.
- Dòng đầu gồm $2$ số $n, m$ lần lượt là số lượng vé và số lượng khách hàng.
- Dòng thứ $2$ gồm $h_1, h_2, ..., h_n$ là giá của vé thứ $i$.
- Dòng thứ $3$ gồm $t_1, t_2, ..., t_m$ là giá tối đa mà khách hàng thứ $i$ có thể trả.
- In ra giá mà người thứ $i$ sẽ mua, nếu không có vé thì in ra $-1$.
- $1 \le n,m \le 2⋅10^5, 1 \le h_i,t_i \le 10^9$

#### Input

5 3
5 3 7 8 5
4 8 3

#### Output

3
8
-1

:::spoiler **Lời giải**
- Trước tiên chúng ta sẽ sort mảng $h$ lại, sau đó với mỗi khách hàng thứ $i$, ta sẽ dùng tìm kiếm nhị phân để tìm giá vé lớn nhất mà bé hơn $t_i$, thế nhưng khi khách thứ $i$ mua vé đấy rồi chúng ta phải xoá vé đó ra khỏi tập hợp $h$. Tuy nhiên nếu dùng mảng thông thường thì việc xoá sẽ trở nên vô cùng khó khăn vì khi xoá $1$ phần tử khỏi mảng cần mất độ phức tạp cao nhất là $O(n)$ (vốn không khác gì duyệt trâu). Thế nên thay vào đó chúng ta có thể thay thế bằng `multiset` với độ phức tạp để xoá $1$ phần tử là $O(\log{n})$.
- Bạn đọc có thể tìm hiểu thêm về multiset tại [đây](https://www.geeksforgeeks.org/multiset-in-cpp-stl/) để hiểu về cách tìm $1$ phần tử khi sử dụng multiset.
- Cần chú ý khi muốn xoá $1$ phần tử $x$ trong `multiset`, chúng ta cần phải tìm con trỏ của phần tử đó trước rồi mới xoá con trỏ đó đi. Nếu không nó sẽ xoá hết toàn bộ các phần tử $=x$.
- Code mẫu

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll n, m;

void solve()
{
    cin >> n >> m;
    multiset<ll> h; // khai báo tập multiset
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        h.insert(x); // thêm phần tử vào tập multiset
    }
    for (int i = 1; i <= m;++i)
    {
        int t; 
        cin >> t;
        auto pos = h.upper_bound(t);
        if (pos == h.begin())
        { // Nếu con trỏ trả ra phần tử đầu, nghĩa là không còn phần tử nào trước đó <= t, ta trả về -1
            cout << -1 << endl;
            continue;
        }
        --pos; // Lấy con trỏ chỉ vào phần tử <= t
        cout << *pos <<endl;
        h.erase(pos); // xoá phần tử đó
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

- Độ phức tạp của đoạn code trên là $O(m \log{n})$
:::

## Bài 2: [CSES - Factory Machines](https://cses.fi/problemset/task/1620/)
#### Tóm tắt
- Một nhà máy có $n$ máy móc có thể được sử dụng để sản xuất sản phẩm. Mục tiêu là sản xuất ra $t$ sản phẩm, biết máy thứ $i$ sản xuất một sản phẩm trong $k_i$ đơn vị thời gian, các máy có thể sử dụng song song nhau. Hỏi thời gian tối thiểu để sản xuất $t$ sản phẩm là bao nhiêu?
- $1 \le n \le 2*10^5, 1 \le t, k_i \le 10^9$
#### Input

3 7
3 2 5

#### Output

8

#### Giải thích
- Máy $1$ sản xuất $2$ sản phẩm, máy $2$ sản xuất $4$ sản phẩm, máy $3$ sản xuất $1$ sản phẩm. Thời gian tối thiểu để sản xuất $7$ sản phẩm là $max(3*2, 2*4, 5*1) = 8$

:::spoiler **Lời giải**
1. Gọi $x$ (phần tìm $x$ sẽ nằm ở mục $3$ nhé) là thời gian tối thiểu khi sử dụng $n$ máy. Ta cần kiểm tra $x$ có thoả mãn yêu cầu đề bài không?

1.1. Chúng ta cần biết rằng khi dùng thời gian $x$ thì số sản phẩm tạo ra có $\ge t$ sản phẩm mục tiêu hay không? (lí do $\ge t$ bởi vì chúng ta có thể tạo ra đủ hoặc dư là tuỳ ý). Chúng ta cần check $sum(\frac{x}{k_i}) \ge t$ (với $k_i$ là thời gian để tạo ra $1$ sản phẩm của máy thứ $i$)
2. Chúng ta đã có hàm $f(x)$ để check xem $x$ có phải là thời gian thoả. Việc tiếp theo cần làm là kiểm tra xem hàm $f(x)$ có thoả điều kiện để chặt nhị phân hay không?

2.1. Ta thấy rằng nếu $x$ thoả thì với mọi $y \ge x$ cũng thoả. Chứng minh:

$x$ thoả $\Leftrightarrow$ $sum(\frac{x}{k_i}) \ge t$
Mà $x, k_i > 0$
$\Rightarrow$ $sum(\frac{y}{k_i}) \ge sum(\frac{x}{k_i}) \ge t$

2.2. Bài toán tồn tại giá trị $x$ nhỏ nhất.
$\Rightarrow$ Có thể sử dụng tìm kiếm nhị phân.

3. Chúng ta cần tìm biên trái, biên phải hợp lí để kết quả luôn nằm trong phạm vi tìm kiếm

3.1. Ta thấy rằng biên trái (a.k.a thời gian nhỏ nhất có thể có của bài toán) là $0$. Đây là trường hợp nếu $t = 0$ thì chúng ta không cần làm sản phẩm nào hết thì tốn thời gian là $0$

3.2. Ta thấy rằng biên phải (a.k.a thời gian tối đa có thể có của bài toán) sẽ chính là trường hợp $k_i = 10^9, t = 10^9,n=1$ và thời gian tối thiểu cho trường hợp này là $10^{18}$.

4. Chú ý:

4.1. Do biên trái và biên phải có khoảng cách khá lớn nên có khả năng khi tính $m$ sẽ bị tràn số. Thay vì $m = \lfloor\frac{l + r}{2}\rfloor$, chúng ta có thể thay bằng $m = l + \lfloor\frac{r - l}{2}\rfloor$

4.2. Giả sử $n = 2*10^5$ và mọi $k_i = 1$ và $x$ vô cùng lớn $(\le 10^{18})$, trong trường hợp đó khi tính tổng có thể bị tràn. Nhận xét rằng số sản phẩm mục tiêu tối đa chỉ là $10^9$, vậy việc $1$ máy có thể làm ra số lượng sản phẩm $> 10^9$ là không cần thiết, chúng ta chỉ cần lấy $min(\frac{x}{k_i}, 10^9)$ là được.
5. Code mẫu

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 2e5 + 5;

ll n, t, k[maxn];

bool f(ll x)
{
    ll sum = 0;
    for (int i = 1; i <= n; ++i) sum += min(x / k[i], (ll)1e9); // 1e9 = 10^9
    return sum >= t; // Nếu sum >= t return 1 còn không return 0
}

void solve()
{
    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> k[i];
    
    // binary search answer
    ll l = 0, r = 1e18, ans; // 1e18 = 10^18
    while (l <= r)
    {
        ll m = l + (r - l) / 2;
        if (f(m) == 1)
        {
            ans = m;
            r = m - 1;
        } 
        else l = m + 1;
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

- Độ phức tạp thuật toán trên là $O(n\log{10^{18}})$
:::
## Bài 3: [CSES - Array Division](https://cses.fi/problemset/task/1085)
#### Tóm tắt
- Cho một mảng $a$ gồm $n$ số nguyên dương. Tìm cách chia $k$ mảng con liên tiếp sao cho tổng lớn nhất của các mảng con là nhỏ nhất.
- $1 \le k \le n \le 2*10^5, 1 \le x_i \le 10^9$
#### Input

5 3
2 4 7 3 5

#### Output

8

#### Giải thích
Một cách chia tối ưu như sau: $[2, 4], [7], [3, 5]$ và tổng của mỗi mảng con là $6, 7, 8$. Tổng lớn nhất là $8$.

:::spoiler **Lời giải**
1. Tương tự như bài trước, gọi $x$ là giá trị để tồn tại ít nhất $1$ cách chia sao cho $k$ mảng con đều $\le x$. Khi đó, kết quả bài toán trùng với giá trị $x$ nhỏ nhất chúng ta tìm được.

1.1. Chúng ta kiểm tra nếu nhận $x$ là tổng lớn nhất thì có thể chia mảng thành số lượng mảng con $\le k$ ($\le k$ bởi vì ta vẫn có thể lấy các số trong mỗi mảng con ra tạo thành những mảng con mới mà không bị sai đi khẳng định $x$ là tổng lớn nhất) hay không?

1.2. Ta biết được $x$ là tổng lớn nhất, vậy thì khi chia ra các mảng con thì tổng của mỗi mảng con đều phải $\le x$. Chỉ cần duyệt qua $1$ vòng lặp và duy trì tổng $s$ của tập hiện tại xem liệu có quá $x$ hay không, nếu quá $x$ ta tăng biến đếm số lượng mảng con lên 1, hay `cnt++` và reset $s = a_i$ hiện tại.

2. Chúng ta sẽ cần phải kiểm tra xem liệu hàm $f(x)$ có đủ điều kiện để tìm kiếm nhị phân hay không?

2.1. Nếu $x$ hợp lệ thì với mọi $y \ge x$ cũng hợp lệ. Việc chứng minh sẽ để lại cho bạn đọc😁.

2.2. Bài toán tồn tại giá trị $x$ nhỏ nhất.

$\Rightarrow$ Có thể sử dụng tìm kiếm nhị phân.

3. Như bài toán bên trên, chúng ta dễ dàng tìm ra được biên trái $l = 0$ và biên phải $r = s$ với $s$ là tổng các phần tử trong mảng $a$.

4. Code mẫu

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 2e5 + 5;

ll n, k, a[maxn];

bool f(ll x)
{
    int cnt = 0;
    ll s = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > x) return false; // nếu a[i] > x rồi thì chúng ta không cần kiểm tra nữa vì không tồn tại một cách chia thoả mãn
        s += a[i];
        if (s > x)
        { // Nếu tổng s > x thì chúng ta sẽ reset lại s = a[i] đồng thời tăng cnt lên 1
            ++cnt;
            s = a[i];
        }
    }
    ++cnt; // Cộng dãy cuối cùng chưa được kiểm tra
    return cnt <= k;
}

void solve()
{
    cin >> n >> k;
    ll s = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        s += a[i];
    }
    
    ll l = 0, r = s, ans;
    while (l <= r)
    {
        ll m = (l + r) / 2;
        if (f(m) == 1)
        {
            r = m - 1;
            ans = m;
        } 
        else l = m + 1;
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

- Độ phức tạp thuật toán trên là $O(n\log{sum(a)})$
:::
## Bài 4: [TS10 TPHCM - Đào Vàng](https://gdoj.eu.org/problem/chope_daovang)
#### Tóm tắt
- Có $N$ thỏi vàng được đặt ở các vị trí $x_1, x_2, ... x_N$ trên trục nằm ngang. Nếu đặt máy khoan có lực đập $R$ tại vị trí $X$ thì có thể lấy được các thỏi vàng nằm trong khoảng từ $[X - R, X + R]$. Người chơi có tối đa $K$ lần đặt máy. Hãy giúp người chơi chọn lực đập $R$ nhỏ nhất để có thể đào hết $N$ thỏi vàng.
- $K \le 20, N \le 50000, x_i \le 10^9$
#### Subtask
- $20\%$ test ứng với $20\%$ số điểm của bài có $K = 1$ và $N \le 1000$
- $20\%$ test ứng với $20\%$ số điểm của bài có $K = 2$ và $N \le 10000$
- $60\%$ test ứng với $60\%$ số điểm của bài có $K \le 20$ và $N \le 50000$
#### Input 1

6 1
2
20
6
5
4
17

#### Output 1

9

#### Giải thích
Với lực đập $R = 9$, người chơi có thể đặt máy khoan $1$ lần tại điểm $X_1 = 11$.

#### Input 2

6 2
2
20
6
5
4
17

#### Output 2

2

#### Giải thích
Với lực đập $R = 2$, người chơi có thể đặt máy khoan $2$ lần tại $X_1 = 4, X_2 = 18$

:::spoiler Lời giải
##### Subtask 1
- Để dễ thao tác, trước tiên chúng ta cần sắp xếp lại toàn bộ mảng tăng dần.
- Với subtask này, vì chỉ có $1$ lần đặt, chúng ta sẽ đặt máy khoan tại vị trí $X$ và lực đập $R$ bé nhất sao cho chúng ta có thể lấy được thỏi vàng bé nhất và thỏi vàng lớn nhất (hay $x_1$ và $x_N$). Hay ta có hệ phương trình sau:
$$
\begin{cases}
X - R \le x_1 \\
X + R \ge x_N
\end{cases} \\
\Leftrightarrow
\begin{cases}
R - X \ge -x_1 \\
R + X \ge x_N
\end{cases} \\
\Rightarrow
2R \ge x_N - x_1 \\
\Leftrightarrow
R \ge \frac{x_N - x_1}{2}
$$
- Nếu $R = \frac{x_N - x_1}{2}$ thì $R + X = x_N \Leftrightarrow \frac{x_N - x_1}{2} + X = x_N \Leftrightarrow X = \frac{x_1 + x_N}{2}$
- Vậy $R$ nguyên bé nhất là $R = \lceil\frac{x_N - x_1}{2}\rceil \Leftrightarrow X = \lceil\frac{x_1 + x_N}{2}\rceil$ ($X$ sẽ được dùng ở subtask $3$).
- Code mẫu

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 50005;

int n, k;
ll x[maxn];

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> x[i];
    sort(x + 1, x + n + 1);
    cout << (x[n] - x[1] + 1) / 2; // cộng 1 để làm tròn lên, bạn đọc có thể thay bằng hàm ceil nếu cảm thấy khó hiểu, tuy nhiên việc thay hàm ceil có thể dẫn dến sai số nếu bạn đọc không cẩn thận
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

- Độ phức tạp: $O(n\log{n})$
##### Subtask 2
- Chúng ta vẫn sẽ giải như subtask $1$, nhưng chúng ta sẽ duyệt qua $a$ và đặt $2$ máy khoan để lần lượt lấy thỏi $(x_1, x_i)$ và $(x_{i + 1}, x_N)$, ta tính $R = max(R_1, R_2)$ sao cho $R$ là bé nhất.
- Code mẫu

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = (ll)1e18; // 1e18 = 10^18
const int maxn = 50005;

int n, k;
ll x[maxn];

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> x[i];
    sort(x + 1, x + n + 1);
    ll R = INF;
    for (int i = 1; i <= n; ++i)
    {
        ll R1 = (x[i] - x[1] + 1) / 2;
        ll R2 = (x[n] - x[i + 1] + 1) / 2;
        R = min(R, max(R1, R2));
    }
    cout << R;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

- Độ phức tạp: $O(n\log{n})$

##### Subtask 3
- Mục đích để giải những subtask trên chính là tiền đề cho subtask cuối này. Ta thấy rằng khi $k = 2$ thì chúng ta sẽ chia ra làm $2$ đoạn là $(1, i), (i + 1, n)$. Vậy khi chia $3$ đoạn thì sao nhỉ? Chúng ta sẽ chia $(1, i_1), (i_1 + 1, i_2), (i_2 + 1, n)$. Cứ như vậy khi chia $k$ đoạn sẽ là $(1, i_1), (i_1 + 1, i_2), (i_2 + 1, i_3),...,(i_k + 1, n)$. Thế nhưng ta không thể chạy $k$ vòng cho mỗi lần chia được💀.
- Thế nên ta sẽ lật ngược bài toán lại về dạng **có thể tìm kiếm nhị phân như sau:** Gọi $R$ là lực đập mà mọi máy khoan sử dụng để đào $N$ thỏi vàng. Vậy chúng ta sẽ kiểm tra xem nếu sử dụng $R$ thì số lượng máy khoan cần đặt tối thiểu là bao nhiêu?
> Từ bước này có rất nhiều cách giải, khuyên bạn đọc hãy tự tìm cách giải trước khi đọc hướng dẫn dưới đây.😀
- Hướng giải dưới đây áp dụng kĩ thuật $2$ con trỏ để cài đặt. Gọi $cnt$ là số máy khoan cần đặt nếu biết $R$. Ta duy trì $2$ con trỏ $lo, hi$ có khoảng cách dài nhất có thể sao cho tồn tại một cách đặt máy khoan tại $X$ mà có thể lấy tất cả các thỏi vàng trong đoạn từ $[x_{lo}, x_{hi}]$. $X$ tối ưu ở đây chính là $X = \lceil\frac{x_{lo} + x_{hi}}{2}\rceil$ (đã được chứng minh ở subtask $1$). Nếu đặt máy khoan tại $X$ mà có thể bao hết đoạn $[x_{lo}, x_{hi}]$ (thoả điều kiện $X - R \le x_{lo},x_{hi} \le X + R$) thì ta tiếp tục tăng con trỏ $hi$ lên. Nếu đặt máy khoan tại $X$ mà không thể bao hết đoạn $[x_{lo}, x_{hi}]$, ta sẽ đặt máy khoan tại $[x_{lo}, x_{hi - 1}]$ (nghĩa là tăng `cnt` lên $1$) và update $lo = hi$ (nghĩa là chúng ta bắt đầu tại vị trí mới với $1$ máy khoan mới).
- Cuối cùng chỉ cần check xem liệu số máy khoan tối thiểu cần đặt có vượt quá $K$ hay không thôi.
- Sau khi qua $2$ bài ví dụ trên thì ta có thể suy ra được ngay hàm $f(R)$ hoàn toàn có thể sử dụng để tìm kiếm nhị phân. Cách cài đặt nhị phân vẫn như $2$ bài trước, chúng ta sẽ tìm biên trái và biên phải để tìm kiếm nhị phân.
- Biên trái là $0$ bởi vì khi không có thỏi vàng nào, chúng ta không cần đặt máy khoan, do đó $R_{min} = 0$.
- Biên phải là $10^9$ do khi gặp trường hợp $x_{max} - x_{min} = 10^9$, vì vậy $R_{max} = 10^9$.
- Code mẫu

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 50005;

int n, k;
ll x[maxn];

bool f(ll R)
{
    int cnt = 0;
    int lo = 1, hi = 1;
    while (hi <= n)
    {
        ll X = (x[lo] + x[hi] + 1) / 2;
        if ((X - R <= x[lo]) && (x[hi] <= X + R) ++hi;
        else
        {
            lo = hi; 
            ++cnt; 
        }
    }
    ++cnt; // trường hợp còn dãy cuối chưa được xử lí
    return cnt <= k;
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> x[i];
    
    sort(x + 1, x + n + 1);
    ll l = 0, r = 1e9, ans; // 1e9 = 10^9
    while (l <= r)
    {
        ll m = (l + r) / 2;
        if (f(m) == 1)
        {
            ans = m;
            r = m - 1;
        } 
        else l = m + 1;
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

- Độ phức tạp: $O(n\log{n} + n\log{10^9})$
:::