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

實戰練習

這篇來講講 binary search 的實戰應用，有些題目乍看之下跟他無關，但其實用的就是這個技巧，不囉嗦，直接來看題吧。

題目

這是 AtCoder 裡給初學者的練習賽 ABC174 (AtCoder Beginner Contest 174 round) 的第 5 題 Logs。有興趣的可以註冊個帳號去寫寫看，算是個稍微進階的題目。

簡單描述一下問題，就是給你 N 個木頭段，每個長度不等，然後給你 K 次切割的機會，切完之後你會剩下一堆木頭段，而我們只看裡面最長的那一根木頭做為代表，當你用最聰明的切法，能讓這根做為代表的木頭最短到多短？

一個很直觀的觀察就是，我們要讓每根木頭盡可能平均的短，因為只要剩一根特別長，他就會成為代表，其他的就沒意義了。所以直觀的想法可能會是：

1. 從木頭堆中挑出最長的，切兩半
2. 將兩半再放回木頭堆中（等於每次會多一根）
3. 重複步驟 1

而找最長木頭這件事可以交給 Heap 解決，總時間複雜度會是 O(KlogK)。但很不幸的，這個解法不僅時間複雜度不合格（K 最大可能是 10⁹，太大了），答案還根本是錯的。看看以下這個例子：

註：一般比賽時，如果時間複雜度算出來會超過 10⁹ 就大機率不會過了，10⁹*log(10⁹) 必然 TLE (Time Limit Exceeded)

兩根木頭長度分別是 7 與 9，可以切 3 次

現在的做法：

1. 我們先切 9，得到 4.5, 4.5 兩根木頭，木頭堆變成 [7, 4.5, 4.5]
2. 再來切 7，得到 3.5, 3.5 兩根木頭，木頭堆變成 [4.5, 4.5, 3.5, 3.5]
3. 再來切 4.5 得到 2.25, 2.25 兩根木頭，木頭堆變成 [4.5, 3.5, 3.5, 2.25, 2.25]
4. 最終答案是 4.5

正確的做法：

1. 把 7 切一次，得到 [9, 3.5, 3.5]
2. 把 9 切兩次，平均的切成三段，得到 [3.5, 3.5, 3, 3, 3]
3. 最終答案是 3，比上面的 4.5 要來的好

既然此法行不通，該怎麼辦呢？歡迎讀者先試著想想看，再往下看答案。

如果一直糾結在找到一個最聰明的切法，你就會被這題困死了，其實答案是，我根本不需要想該怎樣切，而是反過來去問，如果我希望最後當代表的那根最長木頭，長度小於等於 X，只靠 K 次切割的機會，有可能做到嗎？之後再把 X 從小到大，盲目的一路問上去，直到做不到為止就解決了！

那首先來看看 X 的範圍會在哪：

1. X 的最小值為 1，由於題目要求 rounding up，也就是無條件進位，我們也不可能把木頭切成長度 0，所以無論如何最小可能值會是 1。
2. X 的最大值，就是原本木頭堆裡最長的長度 max A，因為我開始切之後，無論如何都能讓最長的木頭變得更短。

再來看看整個演算法流程：

1. 選定一個 X（從 1 開始）。
2. 跑一個迴圈，掃過原始木頭堆裡的每根木頭，看看要把該木頭切成數根長度小於等於 X 的木頭，要切幾次（這樣才能保證最後沒有超過 X 長度的木頭存在）。
3. 把每根需要切的次數做加總。
4. 如果總和 > K，表示做不到，必須把 X 再調大些，反之代表做得到，可以把 X 調小點。

讓我們再看一次上面的例子

兩根木頭長度分別是 7 與 9，可以切 3 次

1. X 假如是 1，代表最終所有木頭長度不能超過 1，則長度為 7 的木頭需要切 6 次，長度為 9 的需要切 8 次，總共 14 次，大於給定的 3 次，做不到
2. X 假如是 2，代表最終所有木頭長度不能超過 2，則長度為 7 的木頭需要切 3 次，長度為 9 的需要切 4 次，總共 7 次，大於給定的 3 次，做不到
3. X 假如是 3，代表最終所有木頭長度不能超過 3，則長度為 7 的木頭需要切 2 次，長度為 9 的需要切 2 次，總共 4 次，大於給定的 3 次，做不到
4. X 假如是 4，代表最終所有木頭長度不能超過 4，則長度為 7 的木頭需要切 1 次，長度為 9 的需要切 2 次，總共 3 次，等於給定的 3 次，成功！

最終答案就是 4，整個做法是 O(N*maxA)，因為 X 的最大範圍是 1~maxA，而每確定一個 X 需要檢查 N 根木頭。但這樣的時間複雜度仍然不合格，因為 N 最大是 2*10⁵，maxA 則是 10⁹。

怎麼辦呢？該是偉大的二分搜循法登板救援的時機了！寫了這麼久才終於進入正題。先觀察幾個性質：

1. 我們想在區間 [1, maxA] 之中，找到最小的、可以達成要求的位置 X
2. 如果某個 X 可以，那比他更大一定也可以，而某 X 不行，比他更小的也一定不行
3. 承上，這會是一個單調遞增的數列，也可想成是排序過的數列
4. 題目要求最後答案要 rounding up，我們最終答案必然是一個正整數，所以只要嘗試正整數即可

有沒有發現，我們現在要做的事情就是：

把這個最佳結果想像成我們的 target，是不是就等於是在一個遞增的正整數陣列裡面，找到 >= target 的位置中，最小的那一個位置！是不是就是 bisect_left !

註：雖然切割過程會有浮點數出現，但 rounding up 後仍只要嘗試正整數即可。至於需要對浮點數做 binary search 的情境也是有的，我們未來再談。

以下參考程式碼，是不是其實滿簡單的呢

最終時間複雜度會是 O(N*log(maxA))，終於達成要求！

結語

Binary search 是不是很神奇，看起來無關的題目，其實轉個彎，就突然變成標準題了，只要能搞清楚你的條件、需求是什麼，馬上就能想出要用哪一種版本去解決。如果還沒搞清楚的，快回去看前四篇文章，好好弄懂這個看似簡單，卻藏了無數細節，又極為實用的經典演算法吧。

系列連結

1. 基礎介紹
2. 找不到怎麼辦
3. 含有重複值的情境
4. 從 source code 中學習
5. 實戰練習