# Ch17 二分搜尋法
> 搭配 [Leetcode 解題系統](https://leetcode.com/)
##
> 上一章:[回溯法](https://hackmd.io/s/B1Q0_-whQ)
> 下一章:[Stack與Queue](https://hackmd.io/s/BkZaF56Cm)
> 回目錄:[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>二分搜尋法的用途</font>
玩過終極密碼嗎?
對方心裡想一個數字,每當你猜一次
他都要告訴你該往更高還是更低猜
聰明的你會知道,既然對方會告訴你該更高還更低
那麼想要盡快猜出答案時
絕不是慢慢從1和2一個一個猜上去
而是每次都猜中間值
讓每一輪都可以從他的指引淘汰掉一半的可能
同樣的方法也可以用在很多問題上
只要那個問題有以下的性質
1. 他的解是整數
2. 猜錯時可以明確知道該往更高還是更低猜
那麼就可以使用這種每次對半砍的技法
來讓尋找答案的步驟一次就降到$log_2^N$
## <font color='darkblue'>如何使用二分搜尋法</font>
<font color='darkorange'>【例題】</font>
> 給一個由小到大排序好且長度為 10 的陣列
> 請問數字 48 在陣列的第幾格?

我們很容易就能用眼睛判斷出它在第 6 格
而電腦程式必須一格一格確認才能知道它在哪裡
但既然已經知道陣列是從小到大排列好的
我們就可以不需要每格都確認
而是用二分搜尋法來尋找
一開始
從第 0 格到第 9 格都是可能的答案
因此我們有
```cpp=
int left = 0;
int right = 9;
```
然後我們可以看看「中間」的位置,是不是我們要的答案呢?
```cpp=
int mid = (left+right)/2; // mid = 4
```

我們發現第 4 格的數字是 29
小於我們要找的 48
這時我們不但能確定第 4 格不是我們要的答案
連同第 4 格以前的所有格子都不會是我們要的答案了!
因此我們可以把 left 移到第 5 格
代表現在開始
可能的範圍是第 5 格至第 9 格
```cpp=
if(arr[mid]<48)
left = mid+1; // left = 5
```
這時新的「中間」的位置,是不是我們要的答案呢?
```cpp=
int mid = (left+right)/2; // mid = 7
```

我們發現第 7 格的數字是 49
大於我們要找的 48
這時我們不但能確定第 7 格不是我們要的答案
連同第 7 格以後的所有格子都不會是我們要的答案了!
因此我們可以把 right 移到第 6 格
代表現在開始
可能的範圍是第 5 格至第 6 格
```cpp=
if(arr[mid]>48)
right = mid-1; // right = 6
```
這時新的「中間」的位置,是不是我們要的答案呢?
```cpp=
int mid = (left+right)/2; // mid = 5
```

我們發現第 5 格的數字是 32
小於我們要找的 48
這時我們不但能確定第 5 格不是我們要的答案
連同第 5 格以前的所有格子都不會是我們要的答案了!
因此我們可以把 left 移到第 6 格
代表現在開始
可能的範圍是第 6 格至第 6 格
```cpp=
if(arr[mid]<48)
left = mid+1; // left = 6
```
這時新的「中間」的位置,是不是我們要的答案呢?
```cpp=
int mid = (left+right)/2; // mid = 6
```

我們終於在第六格找到所要的 48
可以印出答案了
```cpp=
if(arr[mid]==48)
cout << "48 is at "<<mid<<endl;
```
把剛才出現過的程式都組合起來
就是以下的樣子
```cpp=
int left = 0;
int right = 9;
while(true){ // 找到為止
int mid = (left+right)/2; // 取範圍的中間
if(arr[mid]<28){ // 如果 mid 太小,就把下界縮到 mid+1
left = mid+1;
}
else if(arr[mid]>28){ // 如果 mid 太大,就把上界縮到 mid-1
right = mid-1;
}
else{
cout << "找到了!" << endl;
break;
}
}
```
你也可以自行推演看看
不管想要找的目標在陣列的哪一格
依據這樣的程式都能正確找出來
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 374: 猜數字 ](https://leetcode.com/problems/guess-number-higher-or-lower/)
>
> 對方從1到n的範圍選了一個數字,我們要猜出是什麼數字
> 我們可以呼叫函數 guess(x) 來問他 x 是不是答案
> 如果 x 太大了,他會回傳 -1
> 如果 x 太小了,他會回傳 1
> 如果 x 就是答案,他會回傳 0 來告訴我們
> 我們要回傳找到的答案
注意:在計算中間值 `(left+right)/2` 的時候
`(left+right)` 可能會超出整數範圍導致出現錯誤的數字
因此我們可以算成 `left+(right-left)/2`
結果是一樣的,但可以保證不超出整數範圍
不過剛才示範的這個二分搜尋的用途太狹隘了
其實二分搜尋的用途應該要是很廣泛的!
我們稍微把題目變化一下,像是:
<font color='darkorange'>【例題】</font>
> 給一個由小到大排序好且長度為 10 的陣列
> 請問數字 50 在不在陣列裡呢?
<font color='darkorange'>【例題】</font>
> 給一個由小到大排序好且長度為 10 的陣列
> 請問第一個「大於」33 的數字在陣列的第幾格?
<font color='darkorange'>【例題】</font>
> 給一個數字 N
> 求出讓 a\*a 大於 N 的最小 a
> (不使用 sqrt() 函數)
像這樣千變萬化的題目
用剛才的方法很容易就會把程式寫得花花綠綠亂七八糟
還有各種硬加上去的判斷式
都難以確定是否涵蓋所有可能
因此
這裡提供一個萬用的二分搜尋模板!
你可以依據題目的性質
把在模板上填入相對應的值
並依據題目的性質處理搜到的答案
這樣一來
不管什麼變化的二分搜尋法都能萬無一失了!
## <font color='darkblue'>二分搜尋法的模板 - 找第一個「夠大」的</font>
```cpp=
int left = 最小可能的答案
int right = 最大可能的答案
while(left<right){
int mid = (left+right)/2;
if(mid 太小了){
left = mid+1;
}
else{ // mid 沒有太小
right = mid; // 注意是 mid,不是 mid-1 喔
// 因為此時 mid 並沒有太大,僅只是沒有太小而已
// 也就是說此時的 mid 有可能是答案,我們不剃除它
}
}
// 迴圈結束後,left會等於right
// 這時 left 就會是「第一個」「沒有太小」的位置
// 再依據題目要求來把 left 換算成答案
```
我們來用幾個例題示範看看這個模板
<font color='darkorange'>【例題】</font>
> 給一個由小到大排序好且長度為 10 的陣列
> 請問第一個「大於」33 的數字在陣列的第幾格?

如果是上圖所示的陣列的話,所求的結果應該要是第 6 格
我們先來想想
在這個題目中
最小可能的搜尋結果、最大可能的搜尋結果,分別是多少?
先來看看最小的可能:
如果整個陣列的值都大於33,例如 `[35, 40, 45, 48, 60, 63, 69, 78, 99, 100]`
那麼答案應該要是 0 (第一個大於33個數字在第0格)
再來看看最大的可能:
如果整個陣列的值都小於等於33,例如 `[6, 9, 12, 15, 18, 21, 24, 27, 30, 33]`
那麼「第一個大於 33」的位置應該要在哪裡呢?
由於陣列裡面根本沒有東西大於33
所以我們希望二分搜尋的結果是一個不存在的位置
來讓我們知道「大於33個數字不存在」
我們可以用「最後一格的下一格(也就是第10格)」來表示這個結果
換個角度想
「第n格是第一個大於33的格子」就相當於「總共有n個格子是小於等於33的」
所以當全部10個數字都小於等於33時
宣稱「第10格是第一個大於33的格子」也挺合理的
因此在這題裡面
「最小可能的結果」是 0
「最大可能的結果」是 10
而「mid太小」的定義為 arr[mid]<=33
(因為我們要找第一個大於33 的數字)
因此套上模板後
程式會是
```cpp=
int left = 0;
int right = 10;
while(left<right){
int mid = (left+right)/2;
if(arr[mid]<=33){
left = mid+1;
}
else{ // arr[mid]>33
right = mid;
}
}
// 迴圈結束後,left會等於right
// 這時 left 就會是「第一個大於33」的位置
if(left==10){
cout << "There isn't any element in the array larger than 33" << endl;
}
else{
cout << "The first element larger than 33 is at " << left;
cout << ", which is " << arr[left] << endl;
}
```
你也可以自行推演看看
當目標改成大於其他數字時
這支程式是不是也能正確地找出位置
你也可以試試看
如果目標要找的數字比陣列裡任何其他數字都大時
left 和 right 是不是會正確地停在 10 的位置呢?
要注意的是
當`left==right` 發生時,迴圈就會結束了
**因此 mid 永遠不會有機會等於 right**
所以儘管我們的 right 一開始等於10
我們也無須擔心程式會企圖存取陣列的第10格
<font color='darkorange'>【例題】</font>
> 題目給一個由小到大排序好的陣列 nums 和一個數字 target
> 請問 target 在 nums 裡的第幾個位置呢?
> 如果 target 不在 nums 裡,請回傳 -1
這是 Leetcode 上的題目,連結是 [Leetcode 704](https://leetcode.com/problems/binary-search/)
這題可以用和上一題完全相同的做法
也就是找找看「第一個『大於等於target』的數字在陣列的第幾格」
再看看那一格是不是 target
就知道陣列裡面有沒有 target 了
```cpp=
int left = 0;
int right = nums.size();
while(left<right){
int mid = left + (right-left)/2;
if(nums[mid]<target){ // 要找 >=target 的位置,所以 <target 是太小
left = mid+1;
}
else{ // nums[mid]>=target
right = mid;
}
}
// 迴圈結束後,left會等於right
// 這時 left 就會是「第一個大於等於target」的位置
if(left==nums.size()||arr[left]!=target)
return -1;
else
return left;
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 35: 數字該在哪裡插入 ](https://leetcode.com/problems/search-insert-position/)
>
> 給一個從小排到大的陣列 nums 和一個整數 target
> 請問 target 在 nums 裡的哪個位置呢?
> 如果不在,我們可以將 target 插入 nums 裡的哪個位置,能保持 nums 依照小到大排好呢?
提示:尋找第一個「大於等於」
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 744: 第一個夠大的字母 ](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)
>
> 給一個從小排到大的字元型態的陣列 letters 和一個字元 target
> 請找出第一個比 target 還要大 (b比a大,c比b大...以此類推) 的字元
> 如果 letters 裡的所有字元都不比 target 大,則回傳 letters[0]
提示:字元可以直接比大小 `if(letters[mid]<target) ...`
## <font color='darkblue'>找最後一個「夠小」的</font>
<font color='darkorange'>【例題】</font>
> 給一個由小到大排序好且長度為 10 的陣列
> 請問最後一個「小於」49 的數字在陣列的第幾格?
要找「最後一個**小於**49的數字」
我們可以用上面的模板找「第一個**大於等於**49的數字」在哪裡!
找到之後
只需要把找到的位置再「往前」一格
就會是我們要的「最後一個小於49的數字」了!

```cpp=
int left = 0;
int right = 10;
while(left<right){
int mid = (left+right)/2;
if(arr[mid]<49){
left = mid+1;
}
else{ // arr[mid]>=49
right = mid;
}
}
// 迴圈結束後,left會等於right
// 這時 left 就會是「第一個大於等於49」的位置
// 而 left-1 就會是「最後一個小於49」的位置
cout << "The last element smaller than 49 is at " << left-1;
cout << ", which is " << arr[left-1] << endl;
```
模板真是萬用!
你也可以試試看
如果目標要找的數字比陣列裡任何其他數字都小時
會發生什麼事?
例如找「最後一個小於3的數字」
那麼在迴圈結束後
left 和 right 會等於 0
(因為第一個大於等於3個數字在第0格)
於是 left-1 會是「-1」
由於陣列根本就沒有第 -1 格
那麼「最後一個小於3的數字在陣列的第-1格」代表什麼意思呢?
就代表「陣列裡的數字全部都沒有小於3 」!
## <font color='darkblue'>二分搜尋法的進階題 - 找最小值</font>
二分搜尋法當然不只能在陣列中找東西
也可以解決很多運算問題
舉例來說,在某些找最小值的題目裡
我們可以用二分搜尋法找「第一個夠大的」
<font color='darkorange'>【例題】</font>
> 資訊課本有若干個章節,每個章節有不同的若干頁,用nums表示
> nums[0]代表第0章有幾頁,nums[1]代表第1章有幾頁,以此類推
> 到期末還剩下 threshold 堂課
> 老師和同學們要共同決定一個上課速率(每堂課上幾頁)
> 必須保證到期末之前能夠上完整本課本,且一堂課內不跨章節
> 請問至少要有每堂課幾頁的速率?
>
> 注意一堂課內不跨章節,也就是如果那堂課已經把某章節講完了,就要提早下課,不能提早進入下一章
舉例來說,課本有4章,分別是1, 2, 5, 9頁,到期末前還有6堂課
- 如果一堂課上4頁
- 第 0 章要花一堂課才能上完 1 頁
- 第 1 章要花一堂課才能上完 2 頁
- 第 2 章要花兩堂課才能上完 5 頁
- 第 3 章要花三堂課才能上完 9 頁
- 因此總共要7堂課才夠上,這個速率不夠大
- 如果一堂課上5頁
- 第 0 章要花一堂課才能上完 1 頁
- 第 1 章要花一堂課才能上完 2 頁
- 第 2 章要花一堂課才能上完 5 頁
- 第 3 章要花兩堂課才能上完 9 頁
- 因此總共要5堂課就夠上,這個速率夠大
- 如果一堂課上6頁
- 第 0 章要花一堂課才能上完 1 頁
- 第 1 章要花一堂課才能上完 2 頁
- 第 2 章要花一堂課才能上完 5 頁
- 第 3 章要花兩堂課才能上完 9 頁
- 因此總共要5堂課就夠上,這個速率夠大
根據上述觀察,第一個夠大的速率是一堂課上5頁,因此答案是5
我們可以利用二分搜尋法找出「第一個夠大的速率」
在解題的過程中,我們會需要一個函數來幫忙判斷「這個速率夠大嗎?」
```cpp=
// 算 a/b 的無條件進位到整數
int divide(int a, int b){
return (a-1)/b + 1;
}
// 檢驗 speed 夠不夠大
bool is_speed_enough(vector<int> pages, int given_classes, int speed){
// 算這個速率需要幾堂課才能上完
int needed_classes = 0;
for(int i=0;i<pages.size();i++){
needed_classes += divide(pages[i], speed);
}
// 檢查需要的課堂數是否小於等於我們擁有的課堂數
if(needed_classes <= given_classes) return true;
else return false;
}
```
有了上面這個幫助檢驗「上課速率是否夠大」的函數
我們就可以用二分搜尋法找「第一個夠大」的速率
```cpp=
int left = 1; // 至少要上一頁吧
int right = 1000000; // 題目說了,一章最多一百萬頁,所以我們一堂課至多就是一百萬頁
while(left<right){
int mid = left+(right-left)/2;
if(!is_speed_enough(nums, threshold, mid)) // 速率太小
left = mid+1;
else // 速率夠大
right = mid;
}
return left;
```
以上是 Leetcode 上的題目,連結是 [Leetcode 1283](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/)
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 875: 猴子吃香蕉 ](https://leetcode.com/problems/koko-eating-bananas/)
>
> 有若干堆香蕉,每堆有不同的若干根香蕉,用名為 piles 的陣列表示
> 農場主人再過 h 小時就會回來了
> 猴子希望在這段時間內把香蕉通通吃完
> 請幫猴子決定一個吃香蕉的速率
> 既吃得完,又盡可能吃得慢(最小吃得完的速率)
提示:這題和例題簡直一模一樣
唯一不同的是香蕉最多有十億(1000000000)根
所以要把搜尋的範圍擴大到十億
<font color='darkorange'>【例題】</font>
> 船要在`day`天內運輸完所有的貨物
> 每件貨物重量不同,他們的重量依序用陣列 `weights` 來表示
> 請問船的承重至少要是多少
> 才能在 `day` 天內把所有貨物依序運輸完?
舉例來說,貨物重量分別是 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,共有5天
- 如果船的承重是14,則
- 第一天運 [1, 2, 3, 4] (不能再把5放進來了,會超重)
- 第二天運 [5, 6](不能再把7放進來了,會超重)
- 第三天運 [7](不能再把8放進來了,以下類推)
- 第四天運 [8]
- 第五天運 [9]
- 第六天運 [10]
- 可知 5 天內運不完
- 如果船的承重是15,則
- 第一天運 [1, 2, 3, 4, 5] (不能再把6放進來了,會超重)
- 第二天運 [6, 7](不能再把8放進來了,會超重,以下類推)
- 第三天運 [8]
- 第四天運 [9]
- 第五天運 [10]
- 由此可知 5 天內可運完
由以上觀察可知船至少要有 15 的承重才能在 5 天內運完
我們可以用二分搜尋找出「第一個夠大的承重量」
需要準備寫一個函數幫忙判斷「船的承重是否夠大」
```cpp=
bool ship_enough(const vector<int>& weights, int days, int capacity){
int day_used = 0; // 需要的天數
int current_weight = 0; // 目前裝了多少重量
for(int i=0;i<weights.size();i++){
// 如果船裝不下第i件貨物了
if(current_weight+weights[i]>capacity){
day_used++; // 先把目前的運走,明天再來運這件貨
current_weight = 0; // 明天就是一艘清空後的船
}
// 如果空船都放不下這件貨,直接判定船不夠大
if(weights[i]>capacity) return false;
current_weight+=weights[i]; // 把貨物重量加到當前船裝載的重量上
}
day_used++; // 最後一天也要算進去
if(day_used<=days) return true; // 可以在 days 天內載完
else return false; // 不能
}
```
有了這個函數的幫忙,我們就可以用二分搜尋法
```cpp=
int left = 1;
int right = 25000000; // 所有貨加起來至多重 500*50000
while(left<right){
int mid = left+(right-left)/2;
if(!ship_enough(weights, days, mid)) // 船不夠大
left = mid+1;
else
right = mid; // 船夠大
}
return left;
```
以上是 Leetcode 上的題目,連結是 [Leetcode 1011](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1760: 最大袋的球可以多小 ](https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/)
>
> 有若干袋球,每一袋有不同數量的若干顆球,用陣列 nums 表示
> 我們可以選一袋球把它一分為二,例如一袋5顆可以變成1+4或2+3
> 這樣的操作,至多可以做 maxOperations 次
> 我們的目標是讓操作完畢後最大的一袋「盡可能的小」
> 請問它可以是多小?
提示:找第一個夠大的球數,搭配函數檢驗「這個球數夠大嗎?」:如果我們無法用 maxOperations 次切割來達成這個大小,就代表他太小了
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1482: 最早哪天夠做花束 ](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)
>
> 花園裡有若干朵花,每朵花盛開的日子不同,用陣列 bloomDay 表示
> 每做一個花束,我們需要採已經盛開的花 k 朵,且要是陣列裡連續的 k 朵
> 盛開的花不會謝,但花採了一次就不能再採了
> 我們總共需要 m 個花束
> 請問最早哪一天,花能開到夠做 m 個花束的程度?
提示:找第一個夠大的天數,搭配函數檢驗「這一天已開了的花夠做 m 個花束嗎」
## <font color='darkblue'>二分搜尋法的進階題 - 找最大值</font>
和找最小值類似
在某些找最大值的題目裡
我們可以用二分搜尋法找「最後一個夠小的」
<font color='darkorange'>【例題】</font>
> 給一個數字 N
> 請問 N 開根號後的整數部分是多少?
如果 N 是 3,那麼 $\sqrt N$ 的整數部分就是 1
如果 N 是 10,那麼 $\sqrt N$ 的整數部分就是 3
如果 N 是 0,那麼 $\sqrt N$ 的整數部分就是 0
我們要找的是「最後一個平方不大於N」的數字
根據模板
也就是要找「第一個平方大於N」的數字
再將他減一即為答案
要找「第一個平方大於N的數字」
我們可以大概知道最小可能的答案是1
最大可能的答案是N+1
因此可以令 left 和 right 分別為 1 和 N+1
```cpp=
int left = 1;
int right = N+1;
while(left<right){
int mid = left + (right-left)/2;
if(mid*mid<=N){
left = mid+1;
}
else{ // mid*mid>N
right = mid;
}
}
// 迴圈結束後,left會等於right
// 這時 left 就會是「第一個平方大於N」的數字
// 而 left-1 就會是「最後一個平方不大於N」的位置
cout << "the integer part of the square root of N is " << left-1;
```
你可以測試看看
當 N 等於 3, 10, 或 0 的時候
出來的答案是不是都是對的呢?
以上是 Leetcode 上的題目,連結是 [Leetcode 69](https://leetcode.com/problems/sqrtx/)
有一點麻煩的地方是題目的 N 至多為 $2^{31}-1$,所以 N+1 會超出整數範圍
解決方法是在宣告變數的時候,用 long long 來取代 int
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 367: 完全平方數 ](https://leetcode.com/problems/valid-perfect-square/)
>
> 給一個整數 num,請問他是完全平方數嗎?
可以用例題的方法做,最後檢驗是不是`(left-1)*(left-1)==num`
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 441: 擺放錢幣 ](https://leetcode.com/problems/arranging-coins/)
>
> 我們有 n 個硬幣
> 第一排放1個硬幣
> 第二排放2個硬幣,一直到把n個硬幣全部用完
> 請問最後一個「一整排都有硬幣的一排」是哪一排?
> 
> 如上圖,5個硬幣,最後完整的一排是第2排
>
> 
> 如上圖,8個硬幣,最後完整的一排是第3排
提示:相當於找最大的 k 使得 $(1+k)*k/2<=n$ (三角形數公式)
<font color='darkorange'>【例題】</font>
> 有若干種糖果,每一種都有其價格,用陣列 price 表示
> 我們要從裡面挑 k 個來組成美味糖果籃
> 糖果籃子的美味程度是價格最接近的兩種糖果的價差
> 請問盡可能美味的糖果籃子有多美味?
例如糖果的價格是 [13, 5, 1, 8, 21, 2]
而我們要挑 3 顆
我們可以挑 [13, 5, 21]
這樣美味程度就是 8 (正好 21-13 和 13-5 都是 8)
美味程度太大,我們就挑不出 k 顆糖果來
美味程度夠小才可以,但我們希望盡量美味
我們可以用二分搜尋法找「最後一個夠小的美味程度」
也就是「第一個太大的美味程度」減一
我們需要寫一個函數幫忙檢查「是不是要求太美味了(讓我們無法挑出k顆糖果)」
```cpp=
bool TooTasty(vector<int> price, int k, int diff){ // diff 是價差也就是美味程度
// 我們可以先選最便宜的糖果,然後剩下的糖果從便宜的到貴的一一確認
// 第一個價差夠大的就可以也選起來,重複此過程,就能盡可能選出最多糖果
//
// 第一顆(最便宜那顆)必選
int selected = 1;
int last = price[0];
for(int i=1;i<price.size();i++){
// 如果第 i 顆糖果跟上一個入選的糖果價差太小,就不選第i顆
if(price[i]-last<diff) continue;
// 反之,把第 i 顆選起來
selected++;
last = price[i];
}
if(selected < k) return true; // 是個讓人選不出 k 顆的美味程度
else return false; // 要求不夠高,還能選出 k 顆
}
```
有了這個函數的幫忙,我們就能完成二分搜尋
```cpp=
sort(price.begin(), price.end()); // 記得先把糖果依照價格從小到大排序好!
int left = 1;
int right = 1000000000; // 糖果價格的上限
while(left<right){
int mid = left + (right-left)/2;
if(!TooTasty(price, k, mid)) left = mid+1;
else right = mid;
}
// left 是「第一個太大的美味程度」讓我們無法選出k顆
return left-1; // 所以 left-1 就是「最後一個夠小的美味程度」,能選出k顆且最盡可能美味
```
以上是 Leetcode 上的題目,連結是 [Leetcode 2517](https://leetcode.com/problems/maximum-tastiness-of-candy-basket/)
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Leetcode 1552: 球之間的磁力可以多大 ](https://leetcode.com/problems/magnetic-force-between-two-balls/)
>
> 有若干個球桶,他們在數線上的位置用陣列 position 表示
> 我們要從中挑 m 個桶子放入 m 顆球
> 此系統造成的磁力為距離最近的兩顆球的距離
> 請問可以造成的最大磁力為多少
這一題和例題簡直一模一樣,連上限也正好是10^9
<font color="darkgreen"> 【學生練習題】</font> 雖然是 codeforces 的題目但因為很有趣所以留下來了
> - [ ] [CF911B - Two Cakes](https://codeforces.com/problemset/problem/911/B)
>
> 派對共準備了a片鹹蛋糕和b片甜蛋糕
> 來參加派對的人總共有n位
> 因此你要把這些蛋糕分配到n個盤子上
>
> 每個盤子上都可以有任意多片鹹蛋糕
> 或是任意多片甜蛋糕
> 但是不能一個盤子上又有鹹又有甜
>
> 當你分配完後
> 「最少片蛋糕」的那個盤子會歸你
> 你希望你可以吃多一點蛋糕,因此你會盡量平均分配
> 請問在你的努力之下,你可以吃多少片呢?
我們來分析一下這個問題:
- 如果你能吃到 1 片,代表裝鹹蛋糕的盤子不能超過 a 個;裝甜蛋糕的盤子不能超過 b 個
- 如果你能吃到 2 片,代表裝鹹蛋糕的盤子不能超過 a/2 個;裝甜蛋糕的盤子不能超過 b/2 個
$\vdots$
- 如果你能吃到 x 片,代表裝鹹蛋糕的盤子不能超過 a/x 個;裝甜蛋糕的盤子不能超過 b/x 個
換句話說,要是 a/x+b/x 小於 n,代表你無法吃到 x 片!
因此你要搜尋的是「第一個你吃不到的數量」再減1即是答案
也就是搜尋「第一個符合 a/x+b/x<n 的 x」
(提示:最小可能的值是1,最大可能的值是max(a, b)+1)
##
> 上一章:[回溯法](https://hackmd.io/s/B1Q0_-whQ)
> 下一章:[Stack與Queue](https://hackmd.io/s/BkZaF56Cm)
> 回目錄:[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)