面試不再慌，二分法一文全搞定！

大家好，我是梁唐。

之前剛開始做公衆號的時候發過一篇關於二分法的文章，反響很好。只是當時沒有留言，所以沒辦法和讀者們互動。所以這次開通了留言之後，我會把之前的一些我覺得不錯的文章重新回爐，大家如果有想看的文章也可以在文末給我留言。

一

二分法可以說是鼎鼎大名，哪怕是沒有學過編程的同學，可能也都或多或少地有所耳聞。早在兩千多年前，莊子就搞清楚了二分法的精髓，他說：一尺之棰，日取其半，萬世不竭。從這個角度來說，二分法可能是這個世界上最古老的算法之一了。

二分法不僅在實際中運用廣泛，並且也在面試當中廣泛出現。但是它的思想也非常簡單，就是簡單的折半，也就是每次把候選的區間一分爲二，每次只取其中一半，這樣循環往復直到不可分割爲止。

這裏有一個思維誤區，很多人理解的二分法其實是二分查找。雖然說二分法大多數都是用來查找，但是查找並不是二分法的精髓，二分法的精髓其實就是集合的劃分和選擇，從而來縮小集合的規模。很多題目每次二分的時候並不是嚴格折半，也有些題目並不是簡單的查找，而是要二分之後進行情況的判斷，但不管它形式怎麼變，它的核心都是一樣的。只有抓住了這一點本質，纔可以萬變不離其宗。

正是因爲二分法靈活多變，並且原理簡單，學過編程的都會。所以它非常適合作爲面試時候的考題，很多人會覺得二分法這麼簡單，就算面試或者是筆試的時候考到了，難道還會做不出來嗎？理想情況的確如此，但實際情況可能和大家想的大相徑庭。

不說比較困難的算法題想不出思路，就說最簡單沒有任何難度的純二分，在面試的時候，出錯的寫出 bug 的也大有人在。

很多人會覺得奇怪，二分法這麼簡單的算法，真的有人寫不出來嗎？

還真的有，原因也很簡單，恰恰就是二分法太簡單了。

大家回憶一下就知道了，無論是在算法導論還是在一些其他的算法教材當中，關於二分法的描述都不多，詳細一點的會有一些圖例展示一下二分法的思想，簡單的就用幾句話描述一下原理，最後再展示一下代碼，就完事了。讀者在學的時候也是一樣，看了一眼原理，哦，非常簡單，再看一眼代碼，只有三四行，差不多一眼就能記住，那就丟在一邊吧。到了真正上手的時候，問題一下就暴露了出來。

二

二分法最常見的問題有兩個，一個是二分的區間邊界不清楚，另一個是二分查找的結果不明確。我想，這兩個問題是實現二分法的時候，一定會遇到的。遺憾的是，目前的教材當中對於這兩個問題介紹都不多，都只有代碼，留給讀者自行揣摩。

我們先說第一個問題——邊界

早在小學我們就學過，用 l 表示區間左邊界，r 表示區間右邊界，mid=(l + r) / 2 表示二分的中間點。這個在數學裏非常明確，但在編程的時候，有一個隱藏的問題被忽略了，這個問題就是區間的屬性。說白了，究竟這個區間是閉區間呢，還是開區間呢，還是半開半閉區間或者是半閉半開區間？如果這個問題不想清楚，你會發現在處理邊界的時候非常迷糊，思維繞來繞去就是想不清楚。

舉個例子，首先，二分終止的條件究竟怎麼寫，是 while (l < r) 還是 while (l <= r) 還是別的？還有，在搜索的時候，我們究竟要不要將 a[mid] == v 的情況單獨判斷？我們是判斷 a[mid] < v 還是 a[mid] <= v？假設我們選擇用 a[mid] < v，得到的結果爲 true。我們知道答案應該在區間的右半邊，我們需要捨棄左邊的區間。應該對 l 賦值，但是我們是賦值成 l = m 呢還是 l=m + 1 呢？又是爲什麼呢？

你看，如果 l 和 r 表示的區間不考慮清楚，我們在實際寫代碼的時候就會遇到這樣棘手的問題。坑爹的是，當我們爲這些邊界頭疼的時候，我們並不能意識到這是因爲我們沒有搞清楚表示區間的方法導致的。往往會覺得是自己不夠熟悉。

顯然，要解決這個問題需要確定 l 和 r 表示的區間種類。那麼到底應該選擇什麼區間呢？是左閉右開，還是全閉，還是左開右閉呢？

答案有點出人意料，都行。

理論上來說，不論選什麼樣的區間，只要代碼得當，都是可以的，可以說是完全看個人喜好。不過我個人推薦左閉右開，原因很簡單，這個和編程當中的數組定義的情況一致。我們都知道，在代碼的世界裏，數組是從 0 開始的，一個長度爲 10 的數組，最後一個元素的下標是 9。如果使用左閉右開區間，我們將 l=0，r = 數組長度，就完成了初始化，如果用閉區間，r = 長度 - 1，不免顯得有些多餘。

假設我們確定了使用左閉右開區間，我們再來看前面說的兩個問題。

區間確定了，終止條件也就明確了，左閉右開區間 [l, r) 不爲空的話，r 至少大於等於 l + 1。因爲我們要在區間長度大於 1 的時候執行二分，所以二分的循環條件應該是 while (l + 1 < r)。

那麼 while 裏的判斷條件呢？

我們列舉一下，a[mid] 和 v 的大小關係無非只有三種。

第一種 a[mid] = v，很簡單，mid 就是我們要查找的結果，直接返回。

第二種 a[mid] < v，說明我們應該取右邊的區間，由於 l 的位置可以取到，而 mid 已經不是答案了，所以 l = mid + 1。

第三種 a[mid] > v，應該取左邊的區間，mid 不是答案，但是由於 r 指向的位置本身就不在候選區間裏，所以 r = mid，而不是 mid-1，因爲 mid-1 可能是答案，而 r 處的位置是取不到的。

到這裏，似乎一切完美，我們可以很順利地寫出代碼了。但是還沒有結束，依然還有一個小問題。

前文說了，a[mid] 和 v 的關係有三種，當 a[mid] = v 的時候，我們就找到了答案。從這個角度來看，我們二分的時候，通過 l 和 r 縮小區間的範圍，通過 mid 來尋找答案。但是既然我們已經摺半區間的大小了，那麼當區間長度爲 1 的時候，剩下的就是答案，所以我們完全可以不用判斷 mid 是否是答案，直接縮小區間，直到區間長度爲 1 的時候，剩下的就是答案了。

也不難，我們需要把 a[mid] 小於和等於 v 的兩種情況合併，由於 a[mid] 可能等於 v，所以我們不能跳過 mid 這個位置，l = mid + 1 應該寫成 l = mid，於是整個代碼也就出來了：

def binary_search(a, v):
    l, r = 0, len(a)
    while l + 1 < r:
        m = (l + r) // 2
        if a[m] <= v:
            l = m
        else:
            r = m
    # 通過a[l] == v判斷v不存在與a數組當中的情況
    return l

可能會有同學好奇，如果我不使用左閉右開，而使用閉區間呢，代碼又該怎麼寫？

其實只要把區間想清楚了，寫出來也不難。

def binary_search(a, v):
    l, r = 0, len(a) - 1
    while l <= r:
        m = (l + r) // 2
        if a[m] == v:
            return m
        if a[m] < v:
            l = m + 1
        else:
            r = m - 1
    # 表示不存在
    return -1

不過還有一個小問題，爲什麼閉區間形式的二分法的判斷推薦是 while (l <= r) 呢？換成 while (l < r) 行不行？這個問題就留給大家思考，不妨把答案寫在評論裏。

二分法雖然簡單，但這些細節都理解清楚也並不容易，在算法領域當中，如果細節沒有理解到位，陰溝裏翻船是非常平常的事情。希望今天的文章能對大家有所幫助。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7roX68RV3bYkKZhVBqWDlQ