點(diǎn)贊關(guān)注，不再迷路绊袋，你的支持對(duì)我意義重大毕匀！

Hi，我是丑丑癌别。本文「數(shù)據(jù)結(jié)構(gòu) & 算法」| 導(dǎo)讀 —— 登高博見(jiàn) 已收錄期揪，這里有 Android 進(jìn)階成長(zhǎng)路線筆記 & 博客，歡迎跟著彭丑丑一起成長(zhǎng)规个。（聯(lián)系方式在 GitHub）

前言

二分查找也稱折半查找（Binary Search）凤薛，是一種效率較高的查找方法（對(duì)數(shù)時(shí)間復(fù)雜度），也是面試中經(jīng)车郑考到的問(wèn)題缤苫。雖然它的思想很簡(jiǎn)單，但據(jù)《編程珠璣》所述墅拭，二分查找算法的實(shí)現(xiàn)是極易犯錯(cuò)的活玲，典型的 “一聽(tīng)就懂，一寫(xiě)就錯(cuò)”谍婉。 在算法面試中舒憾，如果能表現(xiàn)出迅速將自己的思考轉(zhuǎn)變?yōu)榇a并清晰寫(xiě)在白板上的能力，你的表現(xiàn)會(huì)優(yōu)于只會(huì)夸夸其談而寫(xiě)不出代碼的人穗熬。

目錄

1. 二分查找基礎(chǔ)

1.1 問(wèn)題描述

二分查找的基本問(wèn)題是：給定一個(gè)無(wú)重復(fù)的有序整型數(shù)組镀迂，數(shù)組大小在 之間，查找目標(biāo)數(shù) t 在數(shù)組中的索引唤蔗，不存在則返回 -1探遵。

1.2 算法描述

二分查找算法的核心思想是：減治窟赏，即逐漸縮小包含目標(biāo)數(shù) t 的數(shù)組范圍（縮小問(wèn)題規(guī)模）來(lái)解決問(wèn)題。

• 1箱季、一開(kāi)始涯穷，數(shù)組范圍是整個(gè)原數(shù)組；
• 2藏雏、將目標(biāo)數(shù)與數(shù)組的中位數(shù)比較拷况，如果中位數(shù)大于目標(biāo)數(shù)，則拋棄數(shù)組的后半部分掘殴，反之拋棄前半部分蝠嘉；
• 3、重復(fù)這個(gè)過(guò)程杯巨，直到找到目標(biāo)數(shù) t 或者數(shù)組范圍為空為止。

例如努酸，下圖演示了在一組數(shù)據(jù)中查找目標(biāo)數(shù) 7 的過(guò)程：

圖片引用自維基百科

1.3 二分查找的優(yōu)勢(shì)

• 1服爷、最省內(nèi)存

二分查找算法基于已排序的原數(shù)組，屬于本地查找算法获诈。而基于二叉堆 / 散列表的查找算法還需要使用額外空間仍源。

• 2、對(duì)數(shù)時(shí)間復(fù)雜度

二分查找的時(shí)間復(fù)雜度僅為舔涎。

1.4 二分查找的局限性

• 1笼踩、依賴于順序表

二分查找算法適用于順序表，而不適用與鏈表亡嫌。這是因?yàn)轫樞虮黼S機(jī)訪問(wèn)元素的時(shí)間復(fù)雜度為嚎于，而鏈表隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為，后者實(shí)現(xiàn)二分查找的時(shí)間復(fù)雜度為挟冠，這比順序遍歷鏈表還慢于购。

• 2、依賴于數(shù)據(jù)有序

二分查找的必要條件之一是數(shù)據(jù)有序知染，否則最低需要的時(shí)間復(fù)雜度進(jìn)行預(yù)先排序（快速排序）肋僧。如果插入 / 刪除操作不頻繁，那么排序操作的時(shí)間成本可以被多次查找操作的成本均攤控淡。這意味著二分查找適合靜態(tài)有序的數(shù)據(jù)類型嫌吠，或者插入 / 刪除不頻繁的動(dòng)態(tài)數(shù)據(jù)數(shù)據(jù)。否則掺炭，應(yīng)該采用二叉堆等動(dòng)態(tài)數(shù)據(jù)類型辫诅。

• 3、不適用數(shù)據(jù)量太大的場(chǎng)景

二分查找依賴于順序表涧狮，意味著存儲(chǔ)數(shù)據(jù)就需要一塊連續(xù)內(nèi)存泥栖。如果程序的內(nèi)存不足以分配這樣一塊連續(xù)的數(shù)組簇宽，那么就無(wú)法使用二分查找。

2. 二分查找解題框架

前面的內(nèi)容相信大家很快就能理解了吧享，我們直接看二分查找的原始題目 704 二分查找 【題解】魏割，并根據(jù)這個(gè)例子來(lái)討論二分查找的解題框架。

給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target  
寫(xiě)一個(gè)函數(shù)搜索 nums 中的 target钢颂，如果目標(biāo)值存在返回下標(biāo)钞它，否則返回 -1。

提示：
你可以假設(shè) nums 中的所有元素是不重復(fù)的殊鞭。
n 將在 [1, 10000]之間遭垛。
nums 的每個(gè)元素都將在 [-9999, 9999]之間。

2.1 解題框架三要素

二分查找解題框架由三個(gè)主要部分組成：

• 1操灿、預(yù)處理

這個(gè)步驟主要處理特殊用例與數(shù)據(jù)預(yù)處理锯仪，對(duì)于特殊用例可以直接返回結(jié)果。而如果數(shù)據(jù)未排序趾盐，則先進(jìn)行排序庶喜。排序過(guò)程一般使用快速排序，時(shí)間復(fù)雜度救鲤，空間復(fù)雜度久窟。

• 2、二分查找

主要思路是做 「排除法」本缠，即：對(duì)于閉區(qū)間斥扛，每次觀察中位數(shù)，根據(jù)中位數(shù)的值丹锹，把區(qū)間劃分為兩個(gè)區(qū)間：

• 一定不包含解的區(qū)間（拋棄）
• 可能包含解的區(qū)間

下一次遍歷時(shí)稀颁，拋棄「一定不包含解的區(qū)間」，而在「可能包含解的區(qū)間」繼續(xù)搜索楣黍。這里會(huì)存在兩種寫(xiě)法峻村，兩種寫(xiě)法劃分的區(qū)別是「區(qū)間范圍是不一樣」。

• 寫(xiě)法 1：嘗試排除左區(qū)間

這種寫(xiě)法嘗試判斷「左區(qū)間」是否存在解锡凝，不存在則拋棄粘昨。此時(shí)，應(yīng)該劃分為：

[left , mid - 1]
[mid , right]

當(dāng)左區(qū)間存在解時(shí)窜锯，下次搜索區(qū)間就是 [left , mid - 1]
當(dāng)左區(qū)間不存在解時(shí)张肾，中位數(shù)卻可能是解，所以下次搜索的區(qū)間需要覆蓋 mid锚扎，即 [mid , right]

• 寫(xiě)法 2：嘗試排除右區(qū)間

這種寫(xiě)法嘗試判斷「右區(qū)間」是否存在解吞瞪，不存在則拋棄。此時(shí)驾孔，應(yīng)該劃分為：

[left , mid]
[mid + 1, right]

當(dāng)右區(qū)間存在解時(shí)芍秆，下次搜索區(qū)間就是 [mid + 1, right]
當(dāng)右區(qū)間不存在解時(shí)惯疙，中位數(shù)卻可能是解，所以下次搜索的區(qū)間需要覆蓋 mid妖啥，即 [left , mid]

一定需要定義閉區(qū)間嗎霉颠？

其實(shí)不是。其他一些解題模板定義了左閉右開(kāi)的區(qū)間荆虱，不過(guò)這樣反而增加了理解的難度蒿偎。要知道一個(gè)左閉右開(kāi)的區(qū)間一定存在一個(gè)等價(jià)的閉區(qū)間，所以在我的模板里怀读，就統(tǒng)一采用了閉區(qū)間啦诉位。

• 3、后處理

在退出循環(huán)以后菜枷，只剩下 1 個(gè)數(shù)未檢查苍糠，如果該元素滿足條件則是目標(biāo)解，否則題目無(wú)解啤誊。

2.2 解題框架

上一節(jié)所述題目參考代碼如下：

參考代碼 1：

fun search(nums: IntArray, target: Int): Int {
    if (nums.size == 0) {
        return -1
    }
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        寫(xiě)法 1：嘗試排除左區(qū)間
        val mid = (left + right) ushr 1
        if (nums[mid] < target) {
            // [mid]嚴(yán)格小于目標(biāo)值岳瞭，不是解
            // 那么，下次搜索區(qū)間為[mid + 1,right]
            left = mid + 1
        } else {
            // [mid]可能是解
            // 那么坷衍，下次搜索區(qū)間為[left,mid]
            right = mid
        }
    }
    return if (nums[left] == target) left else -1
}

參考代碼 2：

fun search(nums: IntArray, target: Int): Int {
    if (nums.size == 0) {
        return -1
    }
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        寫(xiě)法 2：嘗試排除右區(qū)間
        val mid = (left + right + 1) ushr 1
        if (nums[mid] > target) {
            // [mid]嚴(yán)格大于目標(biāo)值，不是解
            // 那么条舔，下次搜索區(qū)間為[left,mid - 1]
            right = mid - 1
        } else {
            // [mid]可能是解
            // 那么枫耳，下次搜索區(qū)間為[mid,right]
            left = mid
        }
    }
    return if (nums[left] == target) left else -1
}

提示： 以上為 Kotlin 代碼，Kotlin 中 shr 和 ushr 是移位運(yùn)算孟抗，shr 是有符號(hào)右移迁杨，ushr 是無(wú)符號(hào)右移。

下面凄硼，我依次分析模板中需要注意的地方：

• 細(xì)節(jié) 1：left = 0铅协，right = nums.size - 1

在 第 2.1 節(jié) 中，我們定義了問(wèn)題為閉區(qū)間摊沉，因此 left 的初值為 0狐史，而 right 的初始值為數(shù)組長(zhǎng)度 - 1。這相對(duì)于其他一些解題模板 right = nums.size 更容易理解说墨，因?yàn)槲覀?left 和 right 永遠(yuǎn)指向我們關(guān)心的區(qū)間骏全。

• 細(xì)節(jié) 2：while(left < right)

表示二分查找的邏輯只處理區(qū)間長(zhǎng)度大于 1 的情況，當(dāng)區(qū)間只剩下一個(gè)元素的時(shí)候尼斧，退出循環(huán)執(zhí)行后處理（如果最后一個(gè)元素滿足條件則是目標(biāo)解姜贡，否則，題目無(wú)解）棺棵。

• 細(xì)節(jié) 3：取中位數(shù)

取中位數(shù)的代碼是mid = (left + right) / 2楼咳，這個(gè)寫(xiě)法是不嚴(yán)謹(jǐn)?shù)南ê础Ｒ驗(yàn)樵?left 或 right 很大的時(shí)候，left + right 有可能發(fā)生溢出母怜，所有較嚴(yán)謹(jǐn)?shù)膶?xiě)法是：

mid = left + (right - left) / 2

另外余耽，/ 2也可以用 移位操作 代替：

mid = (left + right) ushr 1

提示： 可以在 JDK Arrays.java 中看到類似的寫(xiě)法：

int mid = (low + high) >>> 1;

• 細(xì)節(jié) 4：區(qū)間的劃分

在 第 2.1 節(jié) 中，我們介紹了二分查找的兩種寫(xiě)法糙申，要特別理解兩種寫(xiě)法中區(qū)分的劃分方法宾添。

嘗試排除左區(qū)間的寫(xiě)法：

[left , mid - 1] 嘗試拋棄
[mid , right]

即：
left = mid
right = mid - 1

嘗試排除右區(qū)間的寫(xiě)法：

[left , mid]
[mid + 1, right] 嘗試拋棄

即：
left = mid + 1
right = mid

• 細(xì)節(jié) 5：向上取整與向下取整

當(dāng)區(qū)間中含有奇數(shù)個(gè)元素時(shí)，中位數(shù)只有一個(gè)柜裸，例如缕陕，對(duì)于區(qū)間，中位數(shù)是疙挺。而當(dāng)區(qū)間中含有偶數(shù)個(gè)元素時(shí)扛邑，中位數(shù)其實(shí)有兩個(gè)。例如铐然，對(duì)于區(qū)間蔬崩，中位數(shù)是或者。

此時(shí)搀暑，取前一個(gè)中位數(shù)稱為 向下取整沥阳，取后一個(gè)中位數(shù)稱為 向上取整（奇數(shù)區(qū)間向上取整和向下取整是同一個(gè)數(shù)）:

向下取整：
(left + right) ushr 1
left + (right - left) / 2
向上取整：
(left + right + 1) ushr 1
left + (right - left + 1) / 2

那么，我們應(yīng)該選擇哪個(gè)中位數(shù)呢自点，選擇不同中位數(shù)的結(jié)果一樣嗎桐罕？其實(shí)是不一樣的。 這取決于我們?cè)?細(xì)節(jié) 4 中采用的寫(xiě)法：

嘗試排除左區(qū)間的寫(xiě)法：當(dāng)搜索區(qū)間只剩下兩個(gè)元素時(shí)桂敛，應(yīng)該采用向上取整功炮。

「反證法」：因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Bleft%20%2C%20right%5D" alt="[left , right]" mathimg="1">區(qū)間被劃分為： 和 ，如果選擇向下取整（取前一個(gè)中位數(shù)术唬，mid 的值等于 left）薪伏，那么在左區(qū)間 無(wú)法 排除時(shí)，會(huì)進(jìn)入left = mid的分支粗仓。此時(shí)嫁怀，left 和 right 的值沒(méi)有改變，出現(xiàn)區(qū)間不會(huì)縮小的情況借浊，進(jìn)入死循環(huán)眶掌。

嘗試排除右區(qū)間的寫(xiě)法：當(dāng)搜索區(qū)間只剩下兩個(gè)元素時(shí)，應(yīng)該采用向下取整巴碗。

「反證法」：因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Bleft%20%2C%20right%5D" alt="[left , right]" mathimg="1">區(qū)間被劃分為： 和 朴爬，如果選擇向上取整（取后一個(gè)中位數(shù)，mid 的值等于 right）橡淆，那么在右區(qū)間 無(wú)法 排除時(shí)召噩，會(huì)進(jìn)入right = mid的分支母赵。此時(shí)，left 和 right 的值沒(méi)有改變具滴，出現(xiàn)區(qū)間不會(huì)縮小的情況凹嘲，進(jìn)入死循環(huán)。

• 細(xì)節(jié) 6：if (nums[left] == target) left else -1

執(zhí)行后處理：在退出循環(huán)以后构韵，只剩下 1 個(gè)數(shù)未檢查周蹭，如果該元素滿足條件則是目標(biāo)解，否則題目無(wú)解疲恢。

3. 舉一反三

讓我們回顧前面講的二分查找原始題目凶朗，你能找出題目中的關(guān)鍵詞嗎？題目中最關(guān)鍵的信息是：查找無(wú)重復(fù)升序數(shù)組中的目標(biāo)數(shù)显拳，即：

其中棚愤，「無(wú)重復(fù)」和「一個(gè)目標(biāo)數(shù)」不是必要條件，修改這兩個(gè)因素可以延伸出更多題目杂数。

提示： 有序數(shù)組的本質(zhì)是數(shù)組值符合單調(diào)性宛畦，詳見(jiàn) 第 3.5 節(jié)。

3.1 搜索滿足條件的目標(biāo)數(shù)

35. Search Insert Position 【題解】

69. Sqrt(x) 【題解】

162. Find Peak Element (Medium) 【題解】

287. Find the Duplicate Number

374. Guess Number Higher or Lower 【題解】

相對(duì)于【題 704 二分查找】揍移，這類題最大的不同是目標(biāo)數(shù)是「未知數(shù)」次和，要求我們找出這個(gè)目標(biāo)數(shù)。這類題目的差不太大那伐，我們要修正的只不過(guò)是排除區(qū)間的判斷條件踏施，使得下一次搜索的區(qū)間能夠包含滿足條件的目標(biāo)數(shù)即可。

3.2 搜索目標(biāo)數(shù)的邊界

34. Find First and Last Position of Element in Sorted Array (Medium) 【題解】

相對(duì)于【題 704 二分查找】喧锦，這類題最大的不同是數(shù)組存在「重復(fù)」读规，要求我們找出目標(biāo)數(shù)的開(kāi)始位置和結(jié)束位置抓督。我們依舊可以通過(guò)判斷中位數(shù)與目標(biāo)值的關(guān)系燃少，來(lái)確定下一輪的搜索區(qū)間：

• 中位數(shù)嚴(yán)格小于目標(biāo)數(shù)，那么一定不是開(kāi)始位置
• 中位數(shù)嚴(yán)格大于目標(biāo)數(shù)铃在，那么一定不是結(jié)束位置

注意阵具，比較容易出錯(cuò)的是：當(dāng)我們找到一個(gè)與目標(biāo)值相同的位置，再線性地向左和向右搜索目標(biāo)值的邊界定铜，時(shí)間復(fù)雜度是 阳液，而不再是。

3.3 搜索旋轉(zhuǎn)排序數(shù)組

33. Search in Rotated Sorted Array (Medium) 【題解】

81. Search in Rotated Sorted Array II (Medium) 【題解】

相對(duì)于【題 704 二分查找】揣炕，這類題最大的不同是數(shù)組是「旋轉(zhuǎn)排序數(shù)組」帘皿，有序數(shù)組經(jīng)過(guò)旋轉(zhuǎn)后就不再是有序的，我們不能夠直接對(duì)數(shù)組進(jìn)行二分查找畸陡。但如果把數(shù)組看為左右兩個(gè)有序數(shù)組拼接起來(lái)的鹰溜，這兩部分內(nèi)部依舊是有序的虽填，可以使用二分查找。所以我們的解題思路是：判斷當(dāng)前中位數(shù)是的位置：

• 位于左半部分：左邊的元素嚴(yán)格有序曹动，可以采用嘗試拋棄左區(qū)間的寫(xiě)法
• 位于右半部分：右邊的元素嚴(yán)格有序斋日，可以采用嘗試拋棄右區(qū)間的寫(xiě)法

兩種寫(xiě)法的模板我們已經(jīng)很熟悉了，但是需要注意到兩種寫(xiě)法需要用到同一個(gè)中位數(shù)墓陈。而在前面的介紹中我們知道：拋棄左區(qū)間的寫(xiě)法使用前中位數(shù)恶守，拋棄右區(qū)間的寫(xiě)法使用后中位數(shù)，該如何處理呢贡必？其實(shí)我們可以觀察到兔港，在左半部分，區(qū)間 [left,mid] 是嚴(yán)格升序的赊级，等于有 [left,mid - 1]也是升序的押框，所以可以直接使用 mid - 1 對(duì)應(yīng)的前中位數(shù)。

更進(jìn)一步理逊，當(dāng)數(shù)組中存在重復(fù)數(shù)字橡伞，如果中位數(shù)和左端點(diǎn)的數(shù)字相同，那么我們無(wú)法確定目標(biāo)數(shù)是在左區(qū)間完全相同晋被，還是右區(qū)間完全相同兑徘。此時(shí)，我們將 left++ 或者 right--羡洛，相當(dāng)于去掉一個(gè)重復(fù)的干擾項(xiàng)挂脑。

圖片引用自 LeetCode

153. Find Minimum in Rotated Sorted Array (Medium) 【題解】

154. Find Minimum in Rotated Sorted Array II (Hard) 【題解】

這道題不是尋找目標(biāo)值，而是尋找旋轉(zhuǎn)排序數(shù)組中的「最小值」欲侮。用排除法崭闲，我們要做的就是排除一定不存在最小值的區(qū)間：

• 位于左半部分：元素都比區(qū)間最后一個(gè)元素大，拋棄左區(qū)間
• 位于右半部分：中位數(shù)比區(qū)間最后一個(gè)元素大威蕉，拋棄右區(qū)間

更進(jìn)一步刁俭，當(dāng)數(shù)組中存在重復(fù)數(shù)組，如果中位數(shù)和左端點(diǎn)的數(shù)字相同韧涨，那么我們無(wú)法確定是分界點(diǎn)是在左區(qū)間還是右區(qū)間牍戚。與上一個(gè)問(wèn)題類似，我們依舊可以將 left++ 或者 right--虑粥，從而減少一個(gè)重復(fù)的干擾項(xiàng)如孝。

3.4 搜索山脈數(shù)組

1095. Find in Mountain Array (Hard) 【題解】

這道題與搜索旋轉(zhuǎn)排序數(shù)組類似的地方在于：原數(shù)組整體是無(wú)序的，但組成數(shù)組的兩部分內(nèi)部是有序的娩贷。不同之處在于：搜索旋轉(zhuǎn)排序數(shù)組可以通過(guò)比較中位數(shù)的值與的關(guān)系來(lái)判斷當(dāng)前所處的區(qū)間第晰，但是山脈數(shù)組不再成立。

所以我們需要先找到山脈數(shù)組的峰值，再分別在兩個(gè)區(qū)間內(nèi)搜索目標(biāo)值茁瘦。

3.5 最大值極小化

410. Split Array Largest Sum 【題解】

875. Koko Eating Bananas 【題解】

1300. Sum of Mutated Array Closest to Target 【題解】

1482. Minimum Number of Days to Make m Bouquets 【題解】

1552. Magnetic Force Between Two Balls

LCP 12. 小張刷題計(jì)劃 【題解】

這類問(wèn)題也許是二分查找問(wèn)題中最難的罗岖，相對(duì)于【題 704 二分查找】，這類題最大的不同是「沒(méi)有明顯的排序數(shù)組」「沒(méi)有明顯的目標(biāo)數(shù)的條件」腹躁，靈活性非常大桑包，對(duì)于沒(méi)有經(jīng)驗(yàn)的同學(xué)會(huì)很難聯(lián)想到二分查找算法。

對(duì)于這類題目纺非，最重要的點(diǎn)是挖掘題目中隱含的「單調(diào)性」哑了。在前面的題目中大多用到「排序數(shù)組」，其實(shí)排序數(shù)組就隱含了一種單調(diào)性烧颖，即隨著下標(biāo) x 的增大弱左，數(shù)組值單調(diào)遞增或者單調(diào)遞減。

單調(diào)性

單調(diào)性（monotonicity）也可以叫做增減性炕淮，可以定性地描述兩個(gè)變量之間的關(guān)系拆火。當(dāng)變量在其定義區(qū)間內(nèi)增大時(shí)，函數(shù)隨著增大（或減型吭病）们镜，則稱函數(shù) y 在該區(qū)間單調(diào)遞增（或單調(diào)遞減）。

【題 410. 木棍切割問(wèn)題】 是最大值最小化題目的經(jīng)典問(wèn)題：

給定一個(gè)非負(fù)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) m 润歉，你需要將這個(gè)數(shù)組分成 m 個(gè)非空的連續(xù)子數(shù)組模狭。

設(shè)計(jì)一個(gè)算法使得這 m 個(gè)子數(shù)組各自和的最大值最小。

當(dāng)你看到 “最大值最小化” 類似的字樣時(shí)踩衩，你應(yīng)該想一想是不是可以用二分查找解決嚼鹉。那么，怎么挖掘題目中的兩個(gè)變量之間的單調(diào)性呢驱富？

這里有一個(gè)小套路：

• 1锚赤、分析題目中存在那幾個(gè)變量；
• 2褐鸥、找出題目中給出的某個(gè)固定值（例如此題的整數(shù) m）线脚，這個(gè)固定值其實(shí)可以看作一個(gè)限制條件；
• 3晶疼、挖掘變量間的單調(diào)性：當(dāng)變量 1 在區(qū)間內(nèi)遞增時(shí)酒贬，變量 2 單調(diào)遞增或遞減又憨；
• 4翠霍、在變量 1 的區(qū)間內(nèi)執(zhí)行二分搜索，找出滿足限制條件的最小值蠢莺。

例如此題寒匙，經(jīng)過(guò)分析可以看出題目中存在以下幾個(gè)變量：

• 分割數(shù) count
• 最大子數(shù)組和 maxSum

這兩個(gè)變量的單調(diào)性是：當(dāng)「最大子數(shù)組和」減小時(shí)，那么我們就需要多分割幾次，「分割數(shù)」單調(diào)遞增锄弱；而當(dāng)「最大子數(shù)組和」增大時(shí)考蕾，那么我們就不需要?jiǎng)澐帜敲炊啻瘟耍阜指顢?shù)」單調(diào)遞減会宪。

至于二分查找的步驟肖卧，我們要做的是在「最大子數(shù)組和」的取值區(qū)間內(nèi)執(zhí)行二分查找，找到分割數(shù)等于 m 的「目標(biāo)數(shù)」掸鹅。接下來(lái)就是編碼啦塞帐，按照解題框架編寫(xiě)即可。

4. 總結(jié)

如果你也遇到二分查找算法一直寫(xiě)不對(duì)的問(wèn)題巍沙，希望今天介紹的解題框架能對(duì)你有所啟發(fā)葵姥。需要注意，一定要配合練習(xí)才能融會(huì)貫通句携，不要背解題框架榔幸。文章 第 3 節(jié) 整理了大量典型例題，應(yīng)該能覆蓋常見(jiàn)的題型矮嫉，多去看看削咆。最后，歡迎各位大佬們點(diǎn)贊蠢笋、留言态辛、轉(zhuǎn)發(fā)。

參考資料

• 《二分查找詞條》 —— 維基百科
• 《二分查找詳解》 —— labuladong 著
• 《數(shù)據(jù)結(jié)構(gòu)與算法之美》（第15挺尿、16課） —— 王爭(zhēng) jiang奏黑，極客時(shí)間 出品
• 《用「排除法」（減治思想）寫(xiě)二分查找問(wèn)題、與其它二分查找模板的比較》 —— liweiwei1419 著
• 《編程之法·面試和算法心得》（第4章） —— July 著
• 《編程珠璣》（第2编矾、4熟史、9章） —— [美] Jon Bentley 著

創(chuàng)作不易，你的「三連」是丑丑最大的動(dòng)力窄俏，我們下次見(jiàn)蹂匹！