Ch17 二分搜尋法

搭配 Leetcode 解題系統

上一章：回溯法
下一章：Stack與Queue
回目錄：國立科學園區實驗中學C++程式語言自學講義

二分搜尋法的用途

玩過終極密碼嗎?
對方心裡想一個數字，每當你猜一次
他都要告訴你該往更高還是更低猜

聰明的你會知道，既然對方會告訴你該更高還更低
那麼想要盡快猜出答案時
絕不是慢慢從1和2一個一個猜上去
而是每次都猜中間值
讓每一輪都可以從他的指引淘汰掉一半的可能

同樣的方法也可以用在很多問題上
只要那個問題有以下的性質

1. 他的解是整數
2. 猜錯時可以明確知道該往更高還是更低猜

那麼就可以使用這種每次對半砍的技法
來讓尋找答案的步驟一次就降到

$lo{g}_2^N$

如何使用二分搜尋法

【例題】

給一個由小到大排序好且長度為 10 的陣列
請問數字 48 在陣列的第幾格?

我們很容易就能用眼睛判斷出它在第 6 格
而電腦程式必須一格一格確認才能知道它在哪裡
但既然已經知道陣列是從小到大排列好的
我們就可以不需要每格都確認
而是用二分搜尋法來尋找

一開始
從第 0 格到第 9 格都是可能的答案
因此我們有

int left = 0;
int right = 9;

然後我們可以看看「中間」的位置，是不是我們要的答案呢？

int mid = (left+right)/2;   // mid = 4

我們發現第 4 格的數字是 29
小於我們要找的 48
這時我們不但能確定第 4 格不是我們要的答案
連同第 4 格以前的所有格子都不會是我們要的答案了！

因此我們可以把 left 移到第 5 格
代表現在開始
可能的範圍是第 5 格至第 9 格

if(arr[mid]<48)
    left = mid+1;  // left = 5

這時新的「中間」的位置，是不是我們要的答案呢？

int mid = (left+right)/2;   // mid = 7

我們發現第 7 格的數字是 49
大於我們要找的 48
這時我們不但能確定第 7 格不是我們要的答案
連同第 7 格以後的所有格子都不會是我們要的答案了！

因此我們可以把 right 移到第 6 格
代表現在開始
可能的範圍是第 5 格至第 6 格

if(arr[mid]>48)
    right = mid-1;  // right = 6

這時新的「中間」的位置，是不是我們要的答案呢？

int mid = (left+right)/2;   // mid = 5

我們發現第 5 格的數字是 32
小於我們要找的 48
這時我們不但能確定第 5 格不是我們要的答案
連同第 5 格以前的所有格子都不會是我們要的答案了！

因此我們可以把 left 移到第 6 格
代表現在開始
可能的範圍是第 6 格至第 6 格

if(arr[mid]<48)
    left = mid+1;  // left = 6

這時新的「中間」的位置，是不是我們要的答案呢？

int mid = (left+right)/2;   // mid = 6

我們終於在第六格找到所要的 48
可以印出答案了

if(arr[mid]==48)
    cout << "48 is at "<<mid<<endl;

把剛才出現過的程式都組合起來
就是以下的樣子

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;
    }
}

你也可以自行推演看看
不管想要找的目標在陣列的哪一格
依據這樣的程式都能正確找出來

【學生練習題】

• Leetcode 374: 猜數字

對方從1到n的範圍選了一個數字，我們要猜出是什麼數字
我們可以呼叫函數 guess(x) 來問他 x 是不是答案
如果 x 太大了，他會回傳 -1
如果 x 太小了，他會回傳 1
如果 x 就是答案，他會回傳 0 來告訴我們
我們要回傳找到的答案

注意：在計算中間值 (left+right)/2 的時候
(left+right) 可能會超出整數範圍導致出現錯誤的數字
因此我們可以算成 left+(right-left)/2
結果是一樣的，但可以保證不超出整數範圍

不過剛才示範的這個二分搜尋的用途太狹隘了
其實二分搜尋的用途應該要是很廣泛的！

我們稍微把題目變化一下，像是：

【例題】

給一個由小到大排序好且長度為 10 的陣列
請問數字 50 在不在陣列裡呢?

【例題】

給一個由小到大排序好且長度為 10 的陣列
請問第一個「大於」33 的數字在陣列的第幾格?

【例題】

給一個數字 N
求出讓 a*a 大於 N 的最小 a
(不使用 sqrt() 函數)

像這樣千變萬化的題目
用剛才的方法很容易就會把程式寫得花花綠綠亂七八糟
還有各種硬加上去的判斷式
都難以確定是否涵蓋所有可能

因此
這裡提供一個萬用的二分搜尋模板！
你可以依據題目的性質
把在模板上填入相對應的值
並依據題目的性質處理搜到的答案
這樣一來
不管什麼變化的二分搜尋法都能萬無一失了！

二分搜尋法的模板 - 找第一個「夠大」的

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 換算成答案

我們來用幾個例題示範看看這個模板

【例題】

給一個由小到大排序好且長度為 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 的數字)

因此套上模板後
程式會是

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格

【例題】

題目給一個由小到大排序好的陣列 nums 和一個數字 target
請問 target 在 nums 裡的第幾個位置呢？
如果 target 不在 nums 裡，請回傳 -1

這是 Leetcode 上的題目，連結是 Leetcode 704

這題可以用和上一題完全相同的做法
也就是找找看「第一個『大於等於target』的數字在陣列的第幾格」
再看看那一格是不是 target
就知道陣列裡面有沒有 target 了

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;

【學生練習題】

• Leetcode 35: 數字該在哪裡插入

給一個從小排到大的陣列 nums 和一個整數 target
請問 target 在 nums 裡的哪個位置呢？
如果不在，我們可以將 target 插入 nums 裡的哪個位置，能保持 nums 依照小到大排好呢？

提示：尋找第一個「大於等於」

【學生練習題】

• Leetcode 744: 第一個夠大的字母

給一個從小排到大的字元型態的陣列 letters 和一個字元 target
請找出第一個比 target 還要大 (b比a大，c比b大…以此類推) 的字元
如果 letters 裡的所有字元都不比 target 大，則回傳 letters[0]

提示：字元可以直接比大小 if(letters[mid]<target) ...

找最後一個「夠小」的

【例題】

給一個由小到大排序好且長度為 10 的陣列
請問最後一個「小於」49 的數字在陣列的第幾格?

要找「最後一個小於49的數字」
我們可以用上面的模板找「第一個大於等於49的數字」在哪裡！
找到之後
只需要把找到的位置再「往前」一格
就會是我們要的「最後一個小於49的數字」了！

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 」！

二分搜尋法的進階題 - 找最小值

二分搜尋法當然不只能在陣列中找東西
也可以解決很多運算問題
舉例來說，在某些找最小值的題目裡
我們可以用二分搜尋法找「第一個夠大的」

【例題】

資訊課本有若干個章節，每個章節有不同的若干頁，用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

我們可以利用二分搜尋法找出「第一個夠大的速率」
在解題的過程中，我們會需要一個函數來幫忙判斷「這個速率夠大嗎？」

// 算 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;
}

有了上面這個幫助檢驗「上課速率是否夠大」的函數
我們就可以用二分搜尋法找「第一個夠大」的速率

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

【學生練習題】

• Leetcode 875: 猴子吃香蕉

有若干堆香蕉，每堆有不同的若干根香蕉，用名為 piles 的陣列表示
農場主人再過 h 小時就會回來了
猴子希望在這段時間內把香蕉通通吃完
請幫猴子決定一個吃香蕉的速率
既吃得完，又盡可能吃得慢（最小吃得完的速率）

提示：這題和例題簡直一模一樣
唯一不同的是香蕉最多有十億（1000000000）根
所以要把搜尋的範圍擴大到十億

【例題】

船要在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 天內運完
我們可以用二分搜尋找出「第一個夠大的承重量」
需要準備寫一個函數幫忙判斷「船的承重是否夠大」

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; // 不能
}

有了這個函數的幫忙，我們就可以用二分搜尋法

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

【學生練習題】

• Leetcode 1760: 最大袋的球可以多小

有若干袋球，每一袋有不同數量的若干顆球，用陣列 nums 表示
我們可以選一袋球把它一分為二，例如一袋5顆可以變成1+4或2+3
這樣的操作，至多可以做 maxOperations 次
我們的目標是讓操作完畢後最大的一袋「盡可能的小」
請問它可以是多小？

提示：找第一個夠大的球數，搭配函數檢驗「這個球數夠大嗎？」：如果我們無法用 maxOperations 次切割來達成這個大小，就代表他太小了

【學生練習題】

• Leetcode 1482: 最早哪天夠做花束

花園裡有若干朵花，每朵花盛開的日子不同，用陣列 bloomDay 表示
每做一個花束，我們需要採已經盛開的花 k 朵，且要是陣列裡連續的 k 朵
盛開的花不會謝，但花採了一次就不能再採了
我們總共需要 m 個花束
請問最早哪一天，花能開到夠做 m 個花束的程度？

提示：找第一個夠大的天數，搭配函數檢驗「這一天已開了的花夠做 m 個花束嗎」

二分搜尋法的進階題 - 找最大值

和找最小值類似
在某些找最大值的題目裡
我們可以用二分搜尋法找「最後一個夠小的」

【例題】

給一個數字 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

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
有一點麻煩的地方是題目的 N 至多為

$2^{31}-1$，所以 N+1 會超出整數範圍
解決方法是在宣告變數的時候，用 long long 來取代 int

【學生練習題】

• Leetcode 367: 完全平方數

給一個整數 num，請問他是完全平方數嗎？

可以用例題的方法做，最後檢驗是不是(left-1)*(left-1)==num

【學生練習題】

• Leetcode 441: 擺放錢幣

我們有 n 個硬幣
第一排放1個硬幣
第二排放2個硬幣，一直到把n個硬幣全部用完
請問最後一個「一整排都有硬幣的一排」是哪一排？

如上圖，5個硬幣，最後完整的一排是第2排

如上圖，8個硬幣，最後完整的一排是第3排

提示：相當於找最大的 k 使得

$(1+k)\ast k/2<=n$ (三角形數公式)

【例題】

有若干種糖果，每一種都有其價格，用陣列 price 表示
我們要從裡面挑 k 個來組成美味糖果籃
糖果籃子的美味程度是價格最接近的兩種糖果的價差
請問盡可能美味的糖果籃子有多美味？

例如糖果的價格是 [13, 5, 1, 8, 21, 2]
而我們要挑 3 顆
我們可以挑 [13, 5, 21]
這樣美味程度就是 8 （正好 21-13 和 13-5 都是 8）

美味程度太大，我們就挑不出 k 顆糖果來
美味程度夠小才可以，但我們希望盡量美味
我們可以用二分搜尋法找「最後一個夠小的美味程度」
也就是「第一個太大的美味程度」減一

我們需要寫一個函數幫忙檢查「是不是要求太美味了（讓我們無法挑出k顆糖果）」

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 顆
}

有了這個函數的幫忙，我們就能完成二分搜尋

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

【學生練習題】

• Leetcode 1552: 球之間的磁力可以多大

有若干個球桶，他們在數線上的位置用陣列 position 表示
我們要從中挑 m 個桶子放入 m 顆球
此系統造成的磁力為距離最近的兩顆球的距離
請問可以造成的最大磁力為多少

這一題和例題簡直一模一樣，連上限也正好是10^9

【學生練習題】 雖然是 codeforces 的題目但因為很有趣所以留下來了

• CF911B - Two Cakes

派對共準備了a片鹹蛋糕和b片甜蛋糕
來參加派對的人總共有n位
因此你要把這些蛋糕分配到n個盤子上

每個盤子上都可以有任意多片鹹蛋糕
或是任意多片甜蛋糕
但是不能一個盤子上又有鹹又有甜

當你分配完後
「最少片蛋糕」的那個盤子會歸你
你希望你可以吃多一點蛋糕，因此你會盡量平均分配
請問在你的努力之下，你可以吃多少片呢？

我們來分析一下這個問題：

• 如果你能吃到 1 片，代表裝鹹蛋糕的盤子不能超過 a 個；裝甜蛋糕的盤子不能超過 b 個
• 如果你能吃到 2 片，代表裝鹹蛋糕的盤子不能超過 a/2 個；裝甜蛋糕的盤子不能超過 b/2 個
  
  $⋮$
• 如果你能吃到 x 片，代表裝鹹蛋糕的盤子不能超過 a/x 個；裝甜蛋糕的盤子不能超過 b/x 個

換句話說，要是 a/x+b/x 小於 n，代表你無法吃到 x 片！
因此你要搜尋的是「第一個你吃不到的數量」再減1即是答案
也就是搜尋「第一個符合 a/x+b/x<n 的 x」
(提示：最小可能的值是1，最大可能的值是max(a, b)+1)

上一章：回溯法
下一章：Stack與Queue
回目錄：國立科學園區實驗中學C++程式語言自學講義