作者 | 李威

來源 | https://www.liwei.party/

整理?| 五分鐘學算法

全文包含 12000+ 字、30 張高清圖片，預計閱讀時間為 40 分鐘，強烈建議先收藏再仔細閱讀。

正文

下面的動畫以 「力扣」第 704 題：二分查找 為例，展示了使用這個模板編寫二分查找法的一般流程。

binary-search-template-new.gif

以下“演示文稿”展示了本文所要講解的主要內容，您可以只看這部分的內容，如果您還想看得更仔細一點，可以查看“演示文稿”之后的原文。

《十分好用的二分查找法模板》演示文稿

binary-search-template-1.png
binary-search-template-2.png
binary-search-template-3.png
binary-search-template-4.png
binary-search-template-5.png
binary-search-template-6.png
binary-search-template-7.png
binary-search-template-8.png
binary-search-template-9.png
binary-search-template-10.png
binary-search-template-11.png
binary-search-template-12.png
binary-search-template-13.png

（上面的“演示文稿”是對以下文字的概括。）

1、導讀

本文介紹了我這半年以來，在刷題過程中使用“二分查找法”刷題的一個模板，包括這個模板的優點、使用技巧、注意事項、調試方法等。

雖說是模板，但我不打算一開始就貼出代碼，因為這個模板根本沒有必要記憶，只要你能夠理解文中敘述的知識點和注意事項，并加以應用（刷題），相信你會和我一樣喜歡這個模板，并且認為使用它是自然而然的事情。

這個模板應該能夠幫助你解決 LeetCode 帶“二分查找”標簽的常見問題（簡單、中等難度）。

只要你能夠理解文中敘述的知識點和注意事項，并加以應用（其實就是多刷題），相信你會和我一樣喜歡這個模板，并且認為使用它是自然而然的事情。

2、歷史上有關“二分查找法”的故事

二分查找法雖然簡單，但寫好它并沒有那么容易。我們可以看看一些名人關于二分查找法的論述。

• 算法和程序設計技術的先驅 Donald Ervin Knuth（中文名：高德納）：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky …

譯：“雖然二分查找的基本思想相對簡單，但細節可能會非常棘手”。來自維基百科 Binary_search_algorithm，請原諒本人可能非常不優雅的中文翻譯。

• 同樣是高德納先生，在其著作《計算機程序設計的藝術 第 3 卷：排序和查找》中指出：

二分查找法的思想在 1946 年就被提出來了。但是第 1 個沒有 Bug 的二分查找法在 1962 年才出現。

（因時間和個人能力的關系，我沒有辦法提供英文原文，如果能找到英文原文的朋友歡迎提供一下出處，在此先謝過。）

據說這個 Bug 在 Java 的 JDK 中都隱藏了將近 10 年以后，才被人們發現并修復。

• 《編程珠璣》的作者 Jon Bentley：

When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases.

譯：當 JonBentley 把二分查找作為專業程序員課程中的一個問題時，他發現百分之九十的人在花了幾個小時的時間研究之后，沒有提供正確的解決方案，主要是因為錯誤的實現無法正確運行（筆者注：可能返回錯誤的結果，或者出現死循環），或者是不能很好地判斷邊界條件。

3、“傳統的”二分查找法模板的問題

（1）取中位數索引的代碼有問題

int?mid?=?(left?+?right)?/?2?

這行代碼是有問題的，在 left 和 right 都比較大的時候，left + right 很有可能超過 int 類型能表示的最大值，即整型溢出，為了避免這個問題，應該寫成：

int?mid?=?left?+?(right?-?left)?/?2?;

事實上，int mid = left + (right - left) / 2 ?在 right 很大、 left 是負數且很小的時候， right - left 也有可能超過 int 類型能表示的最大值，只不過一般情況下 left 和 right 表示的是數組索引值，left 是非負數，因此 ?right - left ?溢出的可能性很小。

更好的寫法是：

int?mid?=?(left?+?right)?>>>?1?;

原因在后文介紹，請讀者留意：

使用“左邊界索引 + 右邊界索引”，然后“無符號右移 1 位”是推薦的寫法。

（2）循環可以進行的條件寫成 while (left <= right) 時，在退出循環的時候，需要考慮返回 left 還是 right，稍不注意，就容易出錯

以本題（LeetCode 第 35 題：搜索插入位置）為例。

分析：根據題意并結合題目給出的 4 個示例，不難分析出這個問題的等價表述如下：

1、如果目標值（嚴格）大于排序數組的最后一個數，返回這個排序數組的長度，否則進入第 2 點。

2、返回排序數組從左到右，大于或者等于目標值的第 1 個數的索引。

事實上，當給出數組中有很多數和目標值相等的時候，我們返回任意一個與之相等的數的索引值都可以，不過為了簡單起見，也為了方便后面的說明，我們返回第 1 個符合題意的數的索引。

題目告訴你“排序數組”，其實就是在瘋狂暗示你用二分查找法。二分查找法的思想并不難，但寫好一個二分法并不簡單，下面就借著這道題為大家做一個總結。

剛接觸二分查找法的時候，我們可能會像下面這樣寫代碼，我把這種寫法容易出錯的地方寫在了注釋里：

參考代碼：針對本題（LeetCode 第 35 題）

public?class?Solution3?{public?int?searchInsert(int[]?nums,?int?target)?{int?len?=?nums.length;if?(nums[len?-?1]?<?target)?{return?len;}int?left?=?0;int?right?=?len?-?1;while?(left?<=?right)?{int?mid?=?(left?+?right)?/?2;//?等于的情況最簡單，我們應該放在第?1?個分支進行判斷if?(nums[mid]?==?target)?{return?mid;}?else?if?(nums[mid]?<?target)?{//?題目要我們返回大于或者等于目標值的第?1?個數的索引//?此時?mid?一定不是所求的左邊界，//?此時左邊界更新為?mid?+?1left?=?mid?+?1;}?else?{//?既然不會等于，此時?nums[mid]?>?target//?mid?也一定不是所求的右邊界//?此時右邊界更新為?mid?-?1right?=?mid?-?1;}}//?注意：一定得返回左邊界 left，//?如果返回右邊界?right?提交代碼不會通過//?【注意】下面我嘗試說明一下理由，如果你不太理解下面我說的，那是我表達的問題//?但我建議你不要糾結這個問題，因為我將要介紹的二分查找法模板，可以避免對返回?left?和?right?的討論//?理由是對于?[1,3,5,6]，target?=?2，返回大于等于?target?的第?1?個數的索引，此時應該返回?1//?在上面的?while?(left?<=?right)?退出循環以后，right?<?left，right?=?0?，left?=?1//?根據題意應該返回?left，//?如果題目要求你返回小于等于?target?的所有數里最大的那個索引值，應該返回?rightreturn?left;} }

說明：

1、當把二分查找法的循環可以進行的條件寫成 while (left <= right) 時，在寫最后一句 return 的時候，如果不假思索，把左邊界 left 返回回去，雖然寫對了，但可以思考一下為什么不返回右邊界 right 呢？

2、但是事實上，返回 left 是有一定道理的，如果題目換一種問法，你可能就要返回右邊界 right，這句話不太理解沒有關系，我也不打算講得很清楚（在上面代碼的注釋中我已經解釋了原因），因為實在太繞了，這不是我要說的重點。

由此，我認為“傳統二分查找法模板”使用的痛點在于：

傳統二分查找法模板，當退出 while 循環的時候，在返回左邊界還是右邊界這個問題上，比較容易出錯。

那么，是不是可以回避這個問題呢？答案是肯定的，答案就在下面我要介紹的“神奇的”二分查找法模板里。

4、“神奇的”二分查找法模板的基本思想

（1）首先把循環可以進行的條件寫成 while(left < right)，在退出循環的時候，一定有 left == right 成立，此時返回 left 或者 right 都可以

或許你會問：退出循環的時候還有一個數沒有看啊（退出循環之前索引 left 或 索引 right 上的值）？

（什么時候需要看最后剩下的那個數，什么時候不需要，會在第 5 點介紹。）

更深層次的思想是“夾逼法”或者稱為“排除法”。

（2）“神奇的”二分查找法模板的基本思想（特別重要）

“排除法”即：在每一輪循環中排除一半以上的元素，于是在對數級別的時間復雜度內，就可以把區間“夾逼” 只剩下 1 個數，而這個數是不是我們要找的數，單獨做一次判斷就可以了。

“夾逼法”或者“排除法”是二分查找算法的基本思想，“二分”是手段，在目標元素不確定的情況下，“二分” 也是“最大熵原理”告訴我們的選擇。

還是 LeetCode 第 35 題，下面給出使用 while (left < right) 模板寫法的 2 段參考代碼，以下代碼的細節部分在后文中會講到，因此一些地方不太明白沒有關系，暫時跳過即可。

參考代碼 1：重點理解為什么候選區間的索引范圍是 [0, size]。

public?class?Solution?{public?int?searchInsert(int[]?nums,?int?target)?{#?返回大于等于?target?的索引，有可能是最后一個int?len?=?nums.length;if?(len?==?0)?{return?0;}int?left?=?0;#?如果?target?比?nums里所有的數都大，則最后一個數的索引?+?1?就是候選值，因此，右邊界應該是數組的長度int?right?=?len;#?二分的邏輯一定要寫對，否則會出現死循環或者數組下標越界while?(left?<?right)?{int?mid?=?left?+?(right?-?left)?/?2;if?(nums[mid]?<?target)?{left?=?mid?+?1;}?else?{right?=?mid;}}return?left;} }

參考代碼 2：對于是否接在原有序數組后面單獨判斷，不滿足的時候，再在候選區間的索引范圍 [0, size - 1] 內使用二分查找法進行搜索。

public?class?Solution?{//?只會把比自己大的覆蓋成小的//?二分法//?如果有一連串數跟?target?相同，則返回索引最靠前的//?特例：3 5 5 5 5 5 5 5 5 5//?特例：3 6 7 8// System.out.println("嘗試過的值："?+ mid);//?1?2?3?5?5?5?5?5?5?6?，target?=?5//?1?2?3?3?5?5?5?6?target?=?4public?int?searchInsert(int[]?nums,?int?target)?{int?len?=?nums.length;if?(len?==?0)?{return?-1;}if?(nums[len?-?1]?<?target)?{return?len;}int?left?=?0;int?right?=?len?-?1;while?(left?<?right)?{int?mid?=?left?+?(right?-?left)?/?2;if?(nums[mid]?<?target)?{//?nums[mid]?的值可以舍棄left?=?mid?+?1;}?else?{//?nums[mid]?不能舍棄right?=?mid;}}return?right;}public?static?void?main(String[]?args)?{int[]?nums?=?{1,?2,?3,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?5,?6};int?target?=?4;Solution2?solution2?=?new?Solution2();int?searchInsert?=?solution2.searchInsert(nums,?target);System.out.println(searchInsert);} }

5、細節、注意事項、調試方法

（1）前提：思考左、右邊界，如果左、右邊界不包括目標數值，會導致錯誤結果

例：LeetCode 第 69 題：x 的平方根

實現 int sqrt(int x) 函數。

計算并返回 x 的平方根，其中 x 是非負整數。

由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

分析：一個非負整數的平方根最小可能是 0 ，最大可能是它自己。

例：LeetCode 第 287 題：尋找重復數

給定一個包含 n + 1 個整數的數組 nums，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數。假設只有一個重復的整數，找出這個重復的數。

分析：題目告訴我們“其數字都在 1 到 n 之間（包括 1 和 n）”。因此左邊界可以取 1 ，右邊界可以取 n。

要注意 2 點：

• 如果 left 和 right 表示的是數組的索引，就要考慮“索引是否有效” ，即“索引是否越界” 是重要的定界依據；

• 左右邊界一定要包括目標元素，例如 LeetCode 第 35 題：“搜索插入位置” ，當 target 比數組中的最后一個數字還要大（不能等于）的時候，插入元素的位置就是數組的最后一個位置 + 1，即 (len - 1 + 1 =) len，如果忽略掉這一點，把右邊界定為 len - 1 ，代碼就不能通過在線測評。

（2）中位數先寫 `int mid = (left + right) >>> 1 ;` 根據循環里分支的編寫情況，再做調整

理解這一點，首先要知道：當數組的元素個數是偶數的時候，中位數有左中位數和右中位數之分。

• 當數組的元素個數是偶數的時候：

使用 int mid = left + (right - left) / 2 ; ?得到左中位數的索引；

使用 int mid = left + (right - left + 1) / 2 ; ?得到右中位數的索引。

• 當數組的元素個數是奇數的時候，以上二者都能選到最中間的那個中位數。

其次，

int?mid?=?left?+?(right?-?left)?/?2?;

int?mid?=?(left?+?right)?>>>?1;

而

int?mid?=?left?+?(right?-?left?+?1)?/?2?;

int?mid?=?(left?+?right?+?1)?>>>?1?

我們使用一個具體的例子來驗證：當左邊界索引 left = 3，右邊界索引 right = 4 的時候，

mid1?=?left?+?(right?-?left)?//?2?=?3?+?(4?-?3)?//?2?=?3?+?0?=?3 mid2?=?left?+?(right?-?left?+?1)?//?2?=?3?+?(4?-?3?+?1)?//?2?=?3?+?1?=?4

左中位數 mid1 是索引 left，右中位數 mid2 是索引 right。

記憶方法：

(right - left) 不加 $1$ 選左中位數，加 $1$ 選右中位數。

那么，什么時候使用左中位數，什么時候使用右中位數呢？選中位數的依據是為了避免死循環，得根據分支的邏輯來選擇中位數，而分支邏輯的編寫也有技巧，下面具體說。

（3）先寫邏輯上容易想到的分支邏輯，這個分支邏輯通常是排除中位數的邏輯；

在邏輯上，“可能是也有可能不是”讓我們感到猶豫不定，但**“一定不是”是我們非常堅決的，通常考慮的因素特別單一，因此“好想” **。在生活中，我們經常聽到這樣的話：找對象時，“有車、有房，可以考慮，但沒有一定不要”；找工作時，“事兒少、離家近可以考慮，但是錢少一定不去”，就是這種思想的體現。

例：LeetCode 第 69 題：x 的平方根

實現 int sqrt(int x) 函數。

計算并返回 x 的平方根，其中 x 是非負整數。

由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

分析：因為題目中說“返回類型是整數，結果只保留整數的部分，小數部分將被舍去”。例如 $5$ 的平方根約等于 $2.236$，在這道題應該返回 $2$。因此如果一個數的平方小于或者等于 x，那么這個數有可能是也有可能不是 x 的平方根，但是能很肯定的是，如果一個數的平方大于 x ，這個數肯定不是 x 的平方根。

注意：先寫“好想”的分支，排除了中位數之后，通常另一個分支就不排除中位數，而不必具體考慮另一個分支的邏輯的具體意義，且代碼幾乎是固定的。

（4）循環內只寫兩個分支，一個分支排除中位數，另一個分支不排除中位數，循環中不單獨對中位數作判斷

既然是“夾逼”法，沒有必要在每一輪循環開始前單獨判斷當前中位數是否是目標元素，因此分支數少了一支，代碼執行效率更高。

以下是“排除中位數的邏輯”思考清楚以后，可能出現的兩個模板代碼。

二分查找法模板

可以排除“中位數”的邏輯，通常比較好想，但并不絕對，這一點視情況而定。

分支條數變成 2 條，比原來 3 個分支要考慮的情況少，好處是：

不用在每次循環開始單獨考慮中位數是否是目標元素，節約了時間，我們只要在退出循環的時候，即左右區間壓縮成一個數（索引）的時候，去判斷這個索引表示的數是否是目標元素，而不必在二分的邏輯中單獨做判斷。

這一點很重要，希望讀者結合具體練習仔細體會，每次循環開始的時候都單獨做一次判斷，在統計意義上看，二分時候的中位數恰好是目標元素的概率并不高，并且即使要這么做，也不是普適性的，不能解決絕大部分的問題。

還以 LeetCode 第 35 題為例，通過之前的分析，我們需要找到“大于或者等于目標值的第 1 個數的索引”。對于這道題而言：

（1）如果中位數小于目標值，它就應該被排除，左邊界 left 就至少是 mid + 1；

（2）如果中位數大于等于目標值，還不能夠肯定它就是我們要找的數，因為要找的是等于目標值的第 $1$ 個數的索引，中位數以及中位數的左邊都有可能是符合題意的數，因此右邊界就不能把 mid 排除，因此右邊界 right 至多是 mid，此時右邊界不向左邊收縮。

下一點就更關鍵了。

（5）根據分支邏輯選擇中位數的類型，可能是左中位數，也可能是右位數，選擇的標準是避免死循環

造成死循環的代碼

死循環容易發生在區間只有 $2$ 個元素時候，此時中位數的選擇尤為關鍵。選擇中位數的依據是：避免出現死循環。我們需要確保：

（下面的這兩條規則說起來很繞，可以暫時跳過）。

1、如果分支的邏輯，在選擇左邊界的時候，不能排除中位數，那么中位數就選“右中位數”，只有這樣區間才會收縮，否則進入死循環；

2、同理，如果分支的邏輯，在選擇右邊界的時候，不能排除中位數，那么中位數就選“左中位數”，只有這樣區間才會收縮，否則進入死循環。

理解上面的這個規則可以通過具體的例子。針對以上規則的第 1 點：如果分支的邏輯，在選擇左邊界的時候不能排除中位數，例如：

偽代碼：

while?left?<?right:#?不妨先寫左中位數，看看你的分支會不會讓你代碼出現死循環，從而調整mid?=?left?+?(right?-?left)?//?2#?業務邏輯代碼if?(check(mid)):#?選擇右邊界的時候，可以排除中位數right?=?mid?-?1else:#?選擇左邊界的時候，不能排除中位數left?=?mid

• 在區間中的元素只剩下 $2$ 個時候，例如：left = 3，right = 4。此時左中位數就是左邊界，如果你的邏輯執行到 left = mid 這個分支，且你選擇的中位數是左中位數，此時左邊界就不會得到更新，區間就不會再收縮（理解這句話是關鍵），從而進入死循環；

• 為了避免出現死循環，你需要選擇中位數是右中位數，當邏輯執行到 left = mid 這個分支的時候，因為你選擇了右中位數，讓邏輯可以轉而執行到 right = mid - 1 讓區間收縮，最終成為 1 個數，退出 while 循環。

上面這段話不理解沒有關系，因為我還沒有舉例子，你有個印象就好，類似地，理解選擇中位數的依據的第 2 點。

（6）退出循環的時候，可能需要對“夾逼”剩下的那個數單獨做一次判斷，這一步稱之為“后處理”。

二分查找法之所以高效，是因為它利用了數組有序的特點，在每一次的搜索過程中，都可以排除將近一半的數，使得搜索區間越來越小，直到區間成為一個數。回到這一節最開始的疑問：“區間左右邊界相等（即收縮成 1 個數）時，這個數是否會漏掉”，解釋如下：

1、如果你的業務邏輯保證了你要找的數一定在左邊界和右邊界所表示的區間里出現，那么可以放心地返回 left 或者 right，無需再做判斷；

2、如果你的業務邏輯不能保證你要找的數一定在左邊界和右邊界所表示的區間里出現，那么只要在退出循環以后，再針對 nums[left] 或者 nums[right] （此時 nums[left] == nums[right]）單獨作一次判斷，看它是不是你要找的數即可，這一步操作常常叫做“后處理”。

• 如果你能確定候選區間里目標元素一定存在，則不必做“后處理”。

例：LeetCode 第 69 題：x 的平方根

實現 int sqrt(int x) 函數。

計算并返回 x 的平方根，其中 x 是非負整數。

由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

分析：非負實數 x 的平方根在 [0, x] 內一定存在，故退出 while (left < right) 循環以后，不必單獨判斷 left 或者 right 是否符合題意。

• 如果你不能確定候選區間里目標元素一定存在，需要單獨做一次判斷。

例：LeetCode 第 704 題：二分查找

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ?，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。

分析：因為目標數有可能不在數組中，當候選區間夾逼成一個數的時候，要單獨判斷一下這個數是不是目標數，如果不是，返回 -1。

（7）取中位數的時候，要避免在計算上出現整型溢出；

int mid = (left + right) / 2; 的問題：在 left 和 right 很大的時候，left + right 會發生整型溢出，變成負數，這是一個 bug ，得改！

int mid = left + (right - left) / 2; 在 right 很大、 left 是負數且很小的時候， right - left 也有可能超過 int 類型能表示的最大值，只不過一般情況下 left 和 right 表示的是數組索引值，left 是非負數，因此 right - left 溢出的可能性很小。因此，它是正確的寫法。下面介紹推薦的寫法。

int mid = (left + right) >>> 1; 如果這樣寫， left + right 在發生整型溢出以后，會變成負數，此時如果除以 $2$ ，mid 是一個負數，但是經過無符號右移，可以得到在不溢出的情況下正確的結果。

解釋“無符號右移”：在 Java 中，無符號右移運算符 >>> 和右移運算符 >> 的區別如下：

• 右移運算符 &gt;&gt; 在右移時，丟棄右邊指定位數，左邊補上符號位；

• 無符號右移運算符 &gt;&gt;&gt; 在右移時，丟棄右邊指定位數，左邊補上 $0$，也就是說，對于正數來說，二者一樣，而負數通過 &gt;&gt;&gt; 后能變成正數。

下面解釋上面的模板中，取中位數的時候使用先用“＋”，然后“無符號右移”。

1、int mid = (left + right) / 2 與 int mid = left + (right - left) / 2 兩種寫法都有整型溢出的風險，沒有哪一個是絕對安全的，注意：這里我們取平均值用的是除以 2，并且是整除：

• int mid = (left + right) / 2 在 left 和 right 都很大的時候會溢出；

• int mid = left + (right - left) / 2 在 right 很大，且 left 是負數且很小的時候會溢出；

2、寫算法題的話，一般是讓你在數組中做二分查找，因此 left 和 right 一般都表示數組的索引，因此 left 在絕大多數情況下不會是負數并且很小，因此使用 ?int mid = left + (right - left) // 2 ?相對 int mid = (left + right) // 2 更安全一些，并且也能向別人展示我們注意到了整型溢出這種情況，但事實上，還有更好的方式；

3、建議使用 int mid = (left + right) >>> 1 這種寫法，其實是大有含義的：

JDK8 中采用 int mid = (left + right) >>> 1 ，重點不在 + ，而在 >>> 。

我們看極端的情況，left 和 high 都是整型最大值的時候，注意，此時 $32$ 位整型最大值它的二進制表示的最高位是 $0$，它們相加以后，最高位是 $1$ ，變成負數，但是再經過無符號右移 >>>（重點是忽略了符號位，空位都以 $0$ 補齊），就能保證使用 + 在整型溢出了以后結果還是正確的。

Java 中 Collections 和 Arrays 提供的 binarySearch 方法，我們點進去看 left 和 right 都表示索引，使用無符號右移又不怕整型溢出，那就用 int mid = (left + right) >>> 1 ?好啦。位運算本來就比使用除法快，這樣看來使用 + 和 <<< 真的是又快又好了。

我想這一點可能是 JDK8 的編寫者們更層次的考量。

看來以后寫算法題，就用 ?int mid = (left + right) >>> 1 吧，反正更多的時候 left 和 right 表示索引。

（8）編碼一旦出現死循環，輸出必要的變量值、分支邏輯是調試的重要方法。

當出現死循環的時候的調試方法：打印輸出左右邊界、中位數的值和目標值、分支邏輯等必要的信息。

按照我的經驗，一開始編碼的時候，稍不注意就很容易出現死循環，不過沒有關系，你可以你的代碼中寫上一些輸出語句，就容易理解“在區間元素只有 2 個的時候容易出現死循環”。

6、總結

總結一下，我愛用這個模板的原因、技巧、優點和注意事項：

（1）原因：

無腦地寫 while left < right: ，這樣你就不用判斷，在退出循環的時候你應該返回 left 還是 right，因為返回 left 或者 right 都對；

（2）技巧：

先寫分支邏輯，并且先寫排除中位數的邏輯分支（因為更多時候排除中位數的邏輯容易想，但是前面我也提到過，這并不絕對），另一個分支的邏輯你就不用想了，寫出第 1 個分支的反面代碼即可（下面的說明中有介紹），再根據分支的情況選擇使用左中位數還是右中位數；

說明：這里再多說一句。如果從代碼可讀性角度來說，只要是你認為好想的邏輯分支，就把它寫在前面，并且加上你的注釋，這樣方便別人理解，而另一個分支，你就不必考慮它的邏輯了。有的時候另一個分支的邏輯并不太好想，容易把自己繞進去。如果你練習做得多了，會形成條件反射。

我簡單總結了一下，左右分支的規律就如下兩點：

• 如果第 1 個分支的邏輯是“左邊界排除中位數”（left = mid + 1），那么第 2 個分支的邏輯就一定是“右邊界不排除中位數”（right = mid），反過來也成立；

• 如果第 2 個分支的邏輯是“右邊界排除中位數”（right = mid - 1），那么第 2 個分支的邏輯就一定是“左邊界不排除中位數”（left = mid），反之也成立。

“反過來也成立”的意思是：如果在你的邏輯中，“邊界不能排除中位數”的邏輯好想，你就把它寫在第 1 個分支，另一個分支是它的反面，你可以不用管邏輯是什么，按照上面的規律直接給出代碼就可以了。能這么做的理論依據就是“排除法”。

（3）優點：

分支條數只有 2 條，代碼執行效率更高，不用在每一輪循環中單獨判斷中位數是否符合題目要求，寫分支的邏輯的目的是盡量排除更多的候選元素，而判斷中位數是否符合題目要求我們放在最后進行，這就是第 5 點；

說明：每一輪循環開始都單獨判斷中位數是否符合要求，這個操作不是很有普適性，因為從統計意義上說，中位數直接就是你想找的數的概率并不大，有的時候還要看看左邊，還要看看右邊。不妨就把它放在最后來看，把候選區間“夾逼”到只剩 $1$ 個元素的時候，視情況單獨再做判斷即可。

（4）注意事項 1：

左中位數還是右中位數選擇的標準根據分支的邏輯而來，標準是每一次循環都應該讓區間收縮，當候選區間只剩下 $2$ 個元素的時候，為了避免死循環發生，選擇正確的中位數類型。如果你實在很暈，不防就使用有 $2$ 個元素的測試用例，就能明白其中的原因，另外在代碼出現死循環的時候，建議你可以將左邊界、右邊界、你選擇的中位數的值，還有分支邏輯都打印輸出一下，出現死循環的原因就一目了然了；

（5）注意事項 2：

如果能確定要找的數就在候選區間里，那么退出循環的時候，區間最后收縮成為 $1$ 個數后，直接把這個數返回即可；如果你要找的數有可能不在候選區間里，區間最后收縮成為 $1$ 個數后，還要單獨判斷一下這個數是否符合題意。

最后給出兩個模板，大家看的時候看注釋，不必也無需記憶它們。

二分查找模板-1.png二分查找模板-2.png

說明：我寫的時候，一般是先默認將中位數寫成左中位數，再根據分支的情況，看看是否有必要調整成右中位數，即是不是要在 (right - left) 這個括號里面加 $1$ 。

雖說是兩個模板，區別在于選中位數，中位數根據分支邏輯來選，原則是區間要收縮，且不出現死循環，退出循環的時候，視情況，有可能需要對最后剩下的數單獨做判斷。

我想我應該是成功地把你繞暈了，如果您覺得啰嗦的地方，就當我是“重要的事情說了三遍”吧，確實是重點的地方我才會重復說。

當然，最好的理解這個模板的方法還是應用它。

在此建議您不妨多做幾道使用“二分查找法”解決的問題，用一下我說的這個模板，在發現問題的過程中，體會這個模板好用的地方，相信你一定會和我一樣愛上這個模板的。

7、應用提升

這里給出一些練習題，這些練習題都可以使用這個“神奇的”二分查找法模板比較輕松地寫出來，并且得到一個不錯的分數，大家加油！

LeetCode 第 704 題

LeetCode 第 69 題

LeetCode 第 153 題

LeetCode 第 154 題

LeetCode 第 287?LeetCode 第 1095 題
LeetCode 第 658 題LeetCode 第 4 題
End

推薦閱讀：（點擊標題即可跳轉）

來和小伙伴們一起向上生長呀！

掃描下方二維碼，添加小詹微信，可領取千元大禮包并申請加入 Python 學習交流群，群內僅供學術交流，日常互動，如果是想發推文、廣告、砍價小程序的敬請繞道！一定記得備注「交流學習」，我會盡快通過好友申請哦！

?長按識別，添加微信

（添加人數較多，請耐心等待）

總結

以上是生活随笔為你收集整理的有了这套模板，女朋友再也不用担心我刷不动 LeetCode 了的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。