二分搜尋法（Binary Search）完整教學（四）

一以貫之

14 min read4 days ago

Update: 這系列原本是在 2020 年寫的，這幾年收穫了很多讀者與朋友回饋，感謝大家，我在 2024 年底又重新整理了一下，把原本的第四篇（從 source code 中學習）移動去第六篇，並補上了這個”新的”第四篇（一以貫之），可以有更好的連貫性，把前三篇學到的技巧與知識總結成一個更統一的思維方式，來理解 Binary Search 的奇妙之處，建議先看完前三篇再看會更清楚喔。

系列連結

基本觀念

如果經過前三篇後，你還是覺得有點亂，覺得還是要記 lower_bound (bisect_left) 跟 upper_bound (bisect_right) 的不同寫法，然後依據情況調整用法，一旦遇到變化的題目，還是感到困難。

到底我們有沒有什麼更一致的概念，可以讓所有題目都用統一的寫法完成？

恭喜，問了就有，我們其實可以把所有問題都用以下模板來解決

bool is_valid(vector<int> &nums, int i) {
  // Is current position i valid?
}

int binary_search_left(vector<int> &nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (is_valid(nums, mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

我們構造一個空的 is_valid function，他的工作是：

判斷現在這個 mid 的 index 位置是否”符合條件”

而判斷條件是什麼？當然就是我們要去好好思考設計的部分啦，這個條件可以五花八門，但最終我們要達到的目標都是要讓整個 array 在這個 is_valid function 的操作下，會得到類似以下的結果：

什麼意思呢，就是我們希望它從某個位置以前全都會是 0 (False)，以後全都會是 1 (True)，如果我們成功構造出這樣的函數，那套用回上面的模板，你的 left 指針最終就會很神奇的停在”第一個 1 ”的位置，也就是你的最終答案回傳值。

實際案例

那這要怎麼使用呢？拿先前的例子套用看看會更好懂，來回想一下我們之前怎樣找 target 的？

先假設我們用 lower_bound，還記得 lower_bound 的精確的定義嗎，是要找大於等於 target 的第一個位置，對吧，也就是下圖這個位置。

那回想一下，當初在 lower_bound 的寫法，如果要套到這個模板上去，這個 is_valid function 是怎麼寫的，是不是以下這樣：

bool is_valid(vector<int> &nums, int i, int target) {
  // 大於等於 target 則回傳 1 (True)，否則回傳 0（False）
  return nums[i] >= target;
}

那這個函數，套用在原本的 array 上面，會是什麼樣子？是不是以下這樣

然後 lower_bound 要的，是不是剛剛好就是 array 經過 is_valid 函數處理後，第一個 1 出現的位置。

神奇吧！

那 upper_bound 又是什麼樣子，我們要的答案是大於 target 的第一個位置，那來看看是不是這樣呢？

程式碼對照過來，is_valid 應該要是長這樣

bool is_valid(vector<int> &nums, int i, int target) {
  // 大於 target 則回傳 1 (True)，否則回傳 0（False）
  return nums[i] > target;
}

這個函數，套用在原本的 array 上面，會是什麼樣子？是不是以下這樣

此時，is_valid 出現的第一個 1 的位置，是不是剛好也就是我們想要的，upper_bound 最終找到的位置！

看到這個想法的厲害之處了吧

不論你來什麼題目，我們就是想辦法構造出正確的 is_valid function，讓他在套到原本的 array 上面後，我們要的目標點剛好是第一個 1 出現的位置，如此一來就做完了。

實戰練習

讓我們用一些更特別的例子來看這個思維的妙用

1. Find Single Peak Element

假設我有一個 Array，前半段是持續遞增的，但到某個最高點後會開始持續遞減，現在假設最高點是唯一的，並且保證任何相鄰的數字不會重複，我想請你用 binary search 的方式，找出那個最高點。

舉例如下圖， [1, 2, 5, 7, 8, 6, 4] 的最高點就是 8

一個特殊狀況是，peak 剛好在最左邊或最右邊，如果這樣的話，答案就給最左或最右即可。

題目敘述完了，所以，這到底該要 lower_bound 還是 upper_bound？第一時間是不是有點搞不清楚，但沒關係，我們不要管他，用這篇講到的新想法試試看如何，我們就想一件事：

我怎樣構造一個函數，可以讓 peak 跟 peak 的右邊全部都是 1，然後左邊全部都是 0。

觀察一下，這兩半邊分別有什麼特性！在右半邊的地方，是不是都是相鄰的兩個數字間，左邊的比右邊的大。而左半邊則否。所以我們很容易可以構造出以下的 is_valid function：

bool is_valid(vector<int> &nums, int i) {
  // 任何相鄰的兩個數字，只要左邊比右邊大，就回傳 1 (True)，不然就回傳 0 (False）
  return (nums[i] > nums[i+1]);
}

但是，要小心！邊界條件很重要，既然我們判斷裡面弄出一個 nums[i+1] ，而且 i 又有可能是最右邊，那就要特別例外處理，以免超出 index 範圍。想想最右邊我們希望他是什麼，因為我們希望 peak 與他的右邊都是 1，假如 peak 剛剛好就在最右邊，當然是回傳 1 對吧。所以最後會得到以下：

bool is_valid(vector<int> &nums, int i) {
  if (i == nums.size() - 1) { 
    // 如果搜尋到最右邊，回傳 1（True）
    return 1
  } else { 
    // 其餘的任何相鄰的兩個數字，只要左邊比右邊大，就回傳 1 (True)，不然就回傳 0 (False）
    return(nums[i] > nums[i+1]);
  }
}

如果想追求更簡潔，也可以寫成這樣

bool is_valid(vector<int> &nums, int i) {
  return (i == nums.size() - 1) or (nums[i] > nums[i+1]);
}

好了，其實你整題已經寫完了，套上原本的模板，拿幾個例子去試試看吧。

如果你目前看懂了，那可以拿以下這個 Leetcode 的題目試試

Leetcode 162: Find Peak Element

這題稍微變化了一下，他有可能有多個 peak，也就是數字可能起起伏伏，而只要相對比左右大的位置都算 peak，並且隨便找到一個都行。可以試著想想看該怎麼辦？

如果有找到方向的話，你應該會發現，這其實跟找一個唯一的 peak 沒什麼本質上的差別。讓我們想一下原本那題為什麼可以 binary search，因為

假如現在是遞增狀態，那他的答案必然在右方
假如現在是遞減狀態，那他的答案必然在左方

而 Leetcode 的這題，其實是非常類似的，只是變成了

假如現在是遞增狀態，那必然“至少有一個答案”在右方
假如現在是遞減狀態，那必然“至少有一個答案”在左方

又，題目允許我們隨便回任一個 peak 都行，因此，由於判斷條件完全一樣，最終的 code 當然也會是一模一樣的，照抄貼上去就好，恭喜你解決了一題 Leetcode Medium 啦。

PS: 如果很細心的話，可能會發現若照著 Leetcode 這個題目的敘述方法，直接把套模板上去，其實 is_valid 的 function 輸出會是 0, 1 交錯出現的，這是因為這題的”目標有多個”，且又“任選一個都行”，算是一個極為特殊的情況。絕大多數時候我們目標都只會有一個，所以不會有 0, 1 交錯的狀況，可以繼續看下題。

2. Single Element in a Sorted Array

再來一題！更進階一點，這次直接上原題

Single Element in a Sorted Array

題目是說，有一個排序好的 Array，但所有數字都是連續出現兩次，只有其中一個數字是單一的，請找出這個單一的數字。

例如 [1, 1, 2, 3, 3, 4, 4, 8, 8] 的答案就是 2

看起來有點嚇人，這題其實有許多很聰明的解法，但我們不需要追求那些，
只要用最直白易懂的方式處理即可，其實越是樸實無華的方式，反而越能以不變應萬變，讓你能舉一反三。

現在，我們的方向，就是要造出一個 is_valid function，可以做到以下結果：紅色框框是目標的 Single Element，我們希望他跟右邊都是 1，而左邊是 0。

怎麼做呢？先好好來觀察一下那個 Single Element 會有什麼特徵吧？

首先根據題目定義，所有“非 Single“的數字，一定是可以在他的左邊或右邊找到跟他一樣的東西，但”Single”的數字，左右一定都跟他不同。這應該是一個很好的起始突破點。

再來，對於那些”非 Single“的數字們，能不能更精確地跟我說，到底是”左邊”，還是”右邊”會一樣？其實是可以的，再好好觀察一下，我們可以發現：

只要在 “Single Element” 的左邊的所有數字，都是

奇數 index 的時候跟左邊一樣，偶數 index 的時候跟右邊一樣

2. 但若是在 “Single Element” 右邊的所有數字，就反過來了，變成是

奇數 index 的時候跟右邊一樣，偶數 index 的時候跟左邊一樣

所以，是不是覺得差不多要做完了，還記得吧，我們的目標就是設計出一個 is_valid function，讓所有”目標”與”目標右邊”都變成 1（True），然後”左邊”都變成 0（False）。怎麼做呢？記得，樸實無華即可

先想想怎樣讓右邊都是 1？

奇數的時候，確認右邊一個跟他一樣，偶數的時候，確認左邊一個跟他一樣，最直白的寫下來就是：

bool is_valid(vector<int> &nums, int i) {
  bool is_odd = i % 2 == 1; // 最簡單的奇偶數判斷方式
  if (is_odd) { // 如果 i 是奇數
     return nums[i] == nums[i+1]
  } else { // 如果 i 是偶數
     return nums[i-1] == nums[i]
  }
}

但，稍微等等，我們除了希望右邊都是 1 以外，也希望我們的”目標”本身是 1 對吧！該怎麼辦呢？

稍微觀察一下，你會發現目標的 Single Element 一定在偶數 index 位置上，所以偶數位置這邊的判斷，讓我稍稍改一下，從”跟左邊一樣”，改成”跟右邊不一樣”，這樣一來，我們目標的 Single Element 那個位置，因為也”跟右邊不一樣”，所以一樣會是 1（True）。

如此一來，就會得到以下的程式碼

bool is_valid(vector<int> &nums, int i) {
  bool is_odd = i % 2 == 1; // 最簡單的奇偶數判斷方式
  if (is_odd) { // 如果 i 是奇數：會跟右邊一樣
     return nums[i] == nums[i+1]
  } else { // 如果 i 是偶數：會跟右邊不一樣
     return nums[i] != nums[i+1]
  }
}

最後，一樣要注意一下邊界條件，當他在最右邊的時候，不要讓 nums[i+1] 超出邊界了，且希望他是 1（因為若目標的 Single Element 剛好在最右邊，我們也希望他是 True），所以最終完整版應該是

bool is_valid(vector<int> &nums, int i) {
  if (i == nums.size() - 1) {
    return 1;
  }

  bool is_odd = i % 2 == 1;
  if (is_odd) { // 如果 i 是奇數：會跟右邊一樣
    return nums[i] == nums[i+1];
  } else { // 如果 i 是偶數：會跟右邊不一樣
    return nums[i] != nums[i+1];
  }
}

就這樣，寫完了！扔回模板上去，我們又默默地寫完了一題看起來很嚇人的Medium 題目了。（PS: 稍微注意一下這題 Leetcode 要的答案是 value 而非 index）

有沒有發現這個想法的驚人之處！這程式碼寫起來可能有點不那麼漂亮，但思維邏輯是相對單純且容易很多的。從頭到尾你都不用煩惱怎樣切半、怎樣移動左界、右界或停止條件等等的煩人問題，而是只專心在造出這個神奇的 is_valid function 即可。

總結

其實，這想法才是 Binary Search 的真諦。如果你以前聽（老師？）說過，Binary Search 必須要在已經排序好的數列中才能使用，這敘述雖然是對的，但略嫌有點狹隘。更廣義的來說，Binary Search 的使用時機是：

對任何一個數列，若存在某個 function，可以讓數列在套上這個 function 後，他的”目標與其右邊”都是 True，而左邊都是 False，那我們就能在這個數列上 Binary Search 目標的位置。

而就實作上來說，我們做的事情其實就是

先把原始的 Array 轉變成一個只有 0 跟 1 的非嚴格遞增數列，然後在上面找第一個 1，也就是數字 1 的 lower_bound。

而本系列前三篇介紹的，在排序好的任意數列中找目標值的問題，使用的就只是這個 is_valid function 最最最簡單的兩種型態：

lower_bound 的 is_valid function：nums[i] >= target
upper_bound 的 is_valid function：nums[i] > target

但我們大可以有各種奇形怪狀的其他型態，只要也能符合上面的定義，他就可以 Binary Search！這個演算法是不是很神奇！

下一篇，就讓我們再來看一個更特別的例子，讓大家感受到 Binary Search 竟然還有這麼神奇的用法存在！

PS: 事實上，我並沒有很喜歡這種教人”套模板”的學習方式，因為如果你只記得模板，而不知道來龍去脈，很可能會一知半解，題目稍稍變化一下就會感到害怕，也可能稍微久沒寫就忘光光。但我們如果有一路從第一章看到這邊，應該已經很清楚 Binary Search 的各種細節與精確的定義方式了，這時候再看這個模板，應該可以讓你更好的全盤理解到底背後都發生了什麼事情。