二分搜索算法運(yùn)用的框架套路

我們前文 我作了首詩(shī)，保你閉著眼睛也能寫(xiě)對(duì)二分查找 詳細(xì)介紹了二分搜索的細(xì)節(jié)問(wèn)題，探討了「搜索一個(gè)元素」，「搜索左側(cè)邊界」，「搜索右側(cè)邊界」這三個(gè)情況，教你如何寫(xiě)出正確無(wú) bug 的二分搜索算法。

但是前文總結(jié)的二分搜索代碼框架僅僅局限于「在有序數(shù)組中搜索指定元素」這個(gè)基本場(chǎng)景，具體的算法問(wèn)題沒(méi)有這么直接，可能你都很難看出這個(gè)問(wèn)題能夠用到二分搜索。

對(duì)于二分搜索算法在具體問(wèn)題中的運(yùn)用，前文 二分搜索的運(yùn)用（一） 和前文 二分搜索的運(yùn)用（二） 有過(guò)介紹，但是還沒(méi)有抽象出來(lái)一個(gè)具體的套路框架。

所以本文就來(lái)總結(jié)一套二分搜索算法運(yùn)用的框架套路，幫你在遇到二分搜索算法相關(guān)的實(shí)際問(wèn)題時(shí)，能夠有條理地思考分析，步步為營(yíng)，寫(xiě)出答案。

警告：本文略長(zhǎng)略硬核，建議清醒時(shí)學(xué)習(xí)。

原始的二分搜索代碼

二分搜索的原型就是在「有序數(shù)組」中搜索一個(gè)元素target，返回該元素對(duì)應(yīng)的索引。

如果該元素不存在，那可以返回一個(gè)什么特殊值，這種細(xì)節(jié)問(wèn)題只要微調(diào)算法實(shí)現(xiàn)就可實(shí)現(xiàn)。

還有一個(gè)重要的問(wèn)題，如果「有序數(shù)組」中存在多個(gè)target元素，那么這些元素肯定挨在一起，這里就涉及到算法應(yīng)該返回最左側(cè)的那個(gè)target元素的索引還是最右側(cè)的那個(gè)target元素的索引，也就是所謂的「搜索左側(cè)邊界」和「搜索右側(cè)邊界」，這個(gè)也可以通過(guò)微調(diào)算法的代碼來(lái)實(shí)現(xiàn)。

我們前文 二分搜索算法框架詳解 詳細(xì)探討了上述問(wèn)題，對(duì)這塊還不清楚的讀者建議復(fù)習(xí)前文，已經(jīng)搞清楚基本二分搜索算法的讀者可以繼續(xù)看下去。

在具體的算法問(wèn)題中，常用到的是「搜索左側(cè)邊界」和「搜索右側(cè)邊界」這兩種場(chǎng)景，很少有讓你單獨(dú)「搜索一個(gè)元素」。

因?yàn)樗惴}一般都讓你求最值，比如前文 二分搜索的運(yùn)用（一） 中說(shuō)的例題讓你求吃香蕉的「最小速度」，讓你求輪船的「最低運(yùn)載能力」，前文 二分搜索的運(yùn)用（二） 講的題就更魔幻了，讓你使每個(gè)子數(shù)組之和的「最大值最小」。

求最值的過(guò)程，必然是搜索一個(gè)邊界的過(guò)程，所以后面我們就詳細(xì)分析一下這兩種搜索邊界的二分算法代碼。

「搜索左側(cè)邊界」的二分搜索算法的具體代碼實(shí)現(xiàn)如下：

// 搜索左側(cè)邊界int left_bound（int［］ nums， int target） {

if （nums.length == 0） return -1;

int left = 0， right = nums.length;

while （left 《 right） {

int mid = left + （right - left） / 2;

if （nums［mid］ == target） {

// 當(dāng)找到 target 時(shí)，收縮右側(cè)邊界

right = mid;

} else if （nums［mid］ 《 target） {

left = mid + 1;

} else if （nums［mid］ 》 target） {

right = mid;

}

}

return left;

}

假設(shè)輸入的數(shù)組nums = ［1，2，3，3，3，5，7］，想搜索的元素target = 3，那么算法就會(huì)返回索引 2。

「搜索右側(cè)邊界」的二分搜索算法的具體代碼實(shí)現(xiàn)如下：

// 搜索右側(cè)邊界int right_bound（int［］ nums， int target） {

if （nums.length == 0） return -1;

int left = 0， right = nums.length;

while （left 《 right） {

int mid = left + （right - left） / 2;

if （nums［mid］ == target） {

// 當(dāng)找到 target 時(shí)，收縮左側(cè)邊界

left = mid + 1;

} else if （nums［mid］ 《 target） {

left = mid + 1;

} else if （nums［mid］ 》 target） {

right = mid;

}

}

return left - 1;

}

輸入同上，那么算法就會(huì)返回索引 4：

好，上述內(nèi)容都屬于復(fù)習(xí)，我想讀到這里的讀者應(yīng)該都能理解。記住上述的圖像，所有能夠抽象出上述圖像的問(wèn)題，都可以使用二分搜索解決。

二分搜索問(wèn)題的泛化

什么問(wèn)題可以運(yùn)用二分搜索算法技巧？

首先，你要從題目中抽象出一個(gè)自變量x，一個(gè)關(guān)于x的函數(shù)f（x），以及一個(gè)目標(biāo)值target。

同時(shí)，x， f（x）， target還要滿(mǎn)足以下條件：

1、f（x）必須是在x上的單調(diào)函數(shù)（單調(diào)增單調(diào)減都可以）。

2、題目是讓你計(jì)算滿(mǎn)足約束條件f（x） == target時(shí)的x的值。

上述規(guī)則聽(tīng)起來(lái)有點(diǎn)抽象，來(lái)舉個(gè)具體的例子：

給你一個(gè)升序排列的有序數(shù)組nums以及一個(gè)目標(biāo)元素target，請(qǐng)你計(jì)算target在數(shù)組中的索引位置，如果有多個(gè)目標(biāo)元素，返回最小的索引。

這就是「搜索左側(cè)邊界」這個(gè)基本題型，解法代碼之前都寫(xiě)了，但這里面x， f（x）， target分別是什么呢？

我們可以把數(shù)組中元素的索引認(rèn)為是自變量x，函數(shù)關(guān)系f（x）就可以這樣設(shè)定：

// 函數(shù) f（x） 是關(guān)于自變量 x 的單調(diào)遞增函數(shù)// 入?yún)?nums 是不會(huì)改變的，所以可以忽略，不算自變量int f（int x， int［］ nums） {

return nums［x］;

}

其實(shí)這個(gè)函數(shù)f就是在訪(fǎng)問(wèn)數(shù)組nums，因?yàn)轭}目給我們的數(shù)組nums是升序排列的，所以函數(shù)f（x）就是在x上單調(diào)遞增的函數(shù)。

最后，題目讓我們求什么來(lái)著？是不是讓我們計(jì)算元素target的最左側(cè)索引？

是不是就相當(dāng)于在問(wèn)我們「滿(mǎn)足f（x） == target的x的最小值是多少」？

如果遇到一個(gè)算法問(wèn)題，能夠把它抽象成這幅圖，就可以對(duì)它運(yùn)用二分搜索算法。

算法代碼如下：

// 函數(shù) f 是關(guān)于自變量 x 的單調(diào)遞增函數(shù)int f（int x， int［］ nums） {

return nums［x］;

}

int left_bound（int［］ nums， int target） {

if （nums.length == 0） return -1;

int left = 0， right = nums.length;

while （left 《 right） {

int mid = left + （right - left） / 2;

if （f（mid， nums） == target） {

// 當(dāng)找到 target 時(shí)，收縮右側(cè)邊界

right = mid;

} else if （f（mid， nums） 《 target） {

left = mid + 1;

} else if （f（mid， nums） 》 target） {

right = mid;

}

}

return left;

}

這段代碼把之前的代碼微調(diào)了一下，把直接訪(fǎng)問(wèn)nums［mid］套了一層函數(shù)f，其實(shí)就是多此一舉，但是，這樣能抽象出二分搜索思想在具體算法問(wèn)題中的框架。

運(yùn)用二分搜索的套路框架

想要運(yùn)用二分搜索解決具體的算法問(wèn)題，可以從以下代碼框架著手思考：

// 函數(shù) f 是關(guān)于自變量 x 的單調(diào)函數(shù)int f（int x） {

// ...

}

// 主函數(shù)，在 f（x） == target 的約束下求 x 的最值int solution（int［］ nums， int target） {

if （nums.length == 0） return -1;

// 問(wèn)自己：自變量 x 的最小值是多少？

int left = ...;

// 問(wèn)自己：自變量 x 的最大值是多少？

int right = ... + 1;

while （left 《 right） {

int mid = left + （right - left） / 2;

if （f（mid） == target） {

// 問(wèn)自己：題目是求左邊界還是右邊界？

// ...

} else if （f（mid） 《 target） {

// 問(wèn)自己：怎么讓 f（x） 大一點(diǎn)？

// ...

} else if （f（mid） 》 target） {

// 問(wèn)自己：怎么讓 f（x） 小一點(diǎn)？

// ...

}

}

return left;

}

具體來(lái)說(shuō)，想要用二分搜索算法解決問(wèn)題，分為以下幾步：

1、確定x， f（x）， target分別是什么，并寫(xiě)出函數(shù)f的代碼。

2、找到x的取值范圍作為二分搜索的搜索區(qū)間，初始化left和right變量。

3、根據(jù)題目的要求，確定應(yīng)該使用搜索左側(cè)還是搜索右側(cè)的二分搜索算法，寫(xiě)出解法代碼。

下面用幾道例題來(lái)講解這個(gè)流程。

例題一、珂珂吃香蕉

珂珂每小時(shí)最多只能吃一堆香蕉，如果吃不完的話(huà)留到下一小時(shí)再吃；如果吃完了這一堆還有胃口，也只會(huì)等到下一小時(shí)才會(huì)吃下一堆。

他想在警衛(wèi)回來(lái)之前吃完所有香蕉，讓我們確定吃香蕉的最小速度K。函數(shù)簽名如下：

int minEatingSpeed（int［］ piles， int H）;

那么，對(duì)于這道題，如何運(yùn)用剛才總結(jié)的套路，寫(xiě)出二分搜索解法代碼？

按步驟思考即可：

1、確定x， f（x）， target分別是什么，并寫(xiě)出函數(shù)f的代碼。

自變量x是什么呢？回憶之前的函數(shù)圖像，二分搜索的本質(zhì)就是在搜索自變量。

所以，題目讓求什么，就把什么設(shè)為自變量，珂珂吃香蕉的速度就是自變量x。

那么，在x上單調(diào)的函數(shù)關(guān)系f（x）是什么？

顯然，吃香蕉的速度越快，吃完所有香蕉堆所需的時(shí)間就越少，速度和時(shí)間就是一個(gè)單調(diào)函數(shù)關(guān)系。

所以，f（x）函數(shù)就可以這樣定義：

若吃香蕉的速度為x根/小時(shí)，則需要f（x）小時(shí)吃完所有香蕉。

代碼實(shí)現(xiàn)如下：

// 定義：速度為 x 時(shí)，需要 f（x） 小時(shí)吃完所有香蕉// f（x） 隨著 x 的增加單調(diào)遞減int f（int［］ piles， int x） {

int hours = 0;

for （int i = 0; i 《 piles.length; i++） {

hours += piles［i］ / x;

if （piles［i］ % x 》 0） {

hours++;

}

}

return hours;

}

target就很明顯了，吃香蕉的時(shí)間限制H自然就是target，是對(duì)f（x）返回值的最大約束。

2、找到x的取值范圍作為二分搜索的搜索區(qū)間，初始化left和right變量。

珂珂吃香蕉的速度最小是多少？多大是多少？

顯然，最小速度應(yīng)該是 1，最大速度是piles數(shù)組中元素的最大值，因?yàn)槊啃r(shí)最多吃一堆香蕉，胃口再大也白搭嘛。

這里可以有兩種選擇，要么你用一個(gè) for 循環(huán)去遍歷piles數(shù)組，計(jì)算最大值，要么你看題目給的約束，piles中的元素取值范圍是多少，然后給right初始化一個(gè)取值范圍之外的值。

我選擇第二種，題目說(shuō)了1 《= piles［i］ 《= 10^9，那么我就可以確定二分搜索的區(qū)間邊界：

public int minEatingSpeed（int［］ piles， int H） {

int left = 1;

// 注意，right 是開(kāi)區(qū)間，所以再加一

int right = 1000000000 + 1;

// ...

}

3、根據(jù)題目的要求，確定應(yīng)該使用搜索左側(cè)還是搜索右側(cè)的二分搜索算法，寫(xiě)出解法代碼。

現(xiàn)在我們確定了自變量x是吃香蕉的速度，f（x）是單調(diào)遞減的函數(shù)，target就是吃香蕉的時(shí)間限制H，題目要我們計(jì)算最小速度，也就是x要盡可能?。?/p>

這就是搜索左側(cè)邊界的二分搜索嘛，不過(guò)注意f（x）是單調(diào)遞減的，不要閉眼睛套框架，需要結(jié)合上圖進(jìn)行思考，寫(xiě)出代碼：

public int minEatingSpeed（int［］ piles， int H） {

int left = 1;

int right = 1000000000 + 1;

while （left 《 right） {

int mid = left + （right - left） / 2;

if （f（piles， mid） == H） {

// 搜索左側(cè)邊界，則需要收縮右側(cè)邊界

right = mid;

} else if （f（piles， mid） 《 H） {

// 需要讓 f（x） 的返回值大一些

right = mid;

} else if （f（piles， mid） 》 H） {

// 需要讓 f（x） 的返回值小一些

left = mid + 1;

}

}

return left;

}

PS：關(guān)于mid是否需要 + 1 的問(wèn)題，前文 二分搜索算法詳解 進(jìn)行了詳細(xì)分析，這里不展開(kāi)了。

至此，這道題就解決了，現(xiàn)在可以把多余的 if 分支合并一下，最終代碼如下：

public int minEatingSpeed（int［］ piles， int H） {

int left = 1;

int right = 1000000000 + 1;

while （left 《 right） {

int mid = left + （right - left） / 2;

if （f（piles， mid） 《= H） {

right = mid;

} else {

left = mid + 1;

}

}

return left;

}

// f（x） 隨著 x 的增加單調(diào)遞減int f（int［］ piles， int x） {

// 見(jiàn)上文

}

PS：我們代碼框架中多余的 if 分支主要是幫助理解的，寫(xiě)出正確解法后建議合并多余的分支，可以提高算法運(yùn)行的效率。

例題二、運(yùn)送貨物

再看看力扣第 1011 題「在 D 天內(nèi)送達(dá)包裹的能力」：

要在D天內(nèi)按順序運(yùn)輸完所有貨物，貨物不可分割，如何確定運(yùn)輸?shù)淖钚≥d重呢？

函數(shù)簽名如下：

int shipWithinDays（int［］ weights， int days）;

和上一道題一樣的，我們按照流程來(lái)就行：

1、確定x， f（x）， target分別是什么，并寫(xiě)出函數(shù)f的代碼。

題目問(wèn)什么，什么就是自變量，也就是說(shuō)船的運(yùn)載能力就是自變量x。

運(yùn)輸天數(shù)和運(yùn)載能力成反比，所以可以讓f（x）計(jì)算x的運(yùn)載能力下需要的運(yùn)輸天數(shù)，那么f（x）是單調(diào)遞減的。

函數(shù)f（x）的實(shí)現(xiàn)如下：

// 定義：當(dāng)運(yùn)載能力為 x 時(shí)，需要 f（x） 天運(yùn)完所有貨物// f（x） 隨著 x 的增加單調(diào)遞減int f（int［］ weights， int x） {

int days = 0;

for （int i = 0; i 《 weights.length; ） {

// 盡可能多裝貨物

int cap = x;

while （i 《 weights.length） {

if （cap 《 weights［i］） break;

else cap -= weights［i］;

i++;

}

days++;

}

return days;

}

對(duì)于這道題，target顯然就是運(yùn)輸天數(shù)D，我們要在f（x） == D的約束下，算出船的最小載重。

2、找到x的取值范圍作為二分搜索的搜索區(qū)間，初始化left和right變量。

船的最小載重是多少？最大載重是多少？

顯然，船的最小載重應(yīng)該是weights數(shù)組中元素的最大值，因?yàn)槊看沃辽俚醚b一件貨物走，不能說(shuō)裝不下嘛。

最大載重顯然就是weights數(shù)組所有元素之和，也就是一次把所有貨物都裝走。

這樣就確定了搜索區(qū)間［left， right）：

public int shipWithinDays（int［］ weights， int days） {

int left = 0;

// 注意，right 是開(kāi)區(qū)間，所以額外加一

int right = 1;

for （int w ： weights） {

left = Math.max（left， w）;

right += w;

}

// ...

}

3、需要根據(jù)題目的要求，確定應(yīng)該使用搜索左側(cè)還是搜索右側(cè)的二分搜索算法，寫(xiě)出解法代碼。

現(xiàn)在我們確定了自變量x是船的載重能力，f（x）是單調(diào)遞減的函數(shù)，target就是運(yùn)輸總天數(shù)限制D，題目要我們計(jì)算船的最小載重，也就是x要盡可能小：

這就是搜索左側(cè)邊界的二分搜索嘛，結(jié)合上圖就可寫(xiě)出二分搜索代碼：

public int shipWithinDays（int［］ weights， int days） {

int left = 0;

// 注意，right 是開(kāi)區(qū)間，所以額外加一

int right = 1;

for （int w ： weights） {

left = Math.max（left， w）;

right += w;

}

while （left 《 right） {

int mid = left + （right - left） / 2;

if （f（weights， mid） == days） {

// 搜索左側(cè)邊界，則需要收縮右側(cè)邊界

right = mid;

} else if （f（weights， mid） 《 days） {

// 需要讓 f（x） 的返回值大一些

right = mid;

} else if （f（weights， mid） 》 days） {

// 需要讓 f（x） 的返回值小一些

left = mid + 1;

}

}

return left;

}

到這里，這道題的解法也寫(xiě)出來(lái)了，我們合并一下多余的 if 分支，提高代碼運(yùn)行速度，最終代碼如下：

public int shipWithinDays（int［］ weights， int days） {

int left = 0;

int right = 1;

for （int w ： weights） {

left = Math.max（left， w）;

right += w;

}

while （left 《 right） {

int mid = left + （right - left） / 2;

if （f（weights， mid） 《= days） {

right = mid;

} else {

left = mid + 1;

}

}

return left;

}

int f（int［］ weights， int x） {

// 見(jiàn)上文

}

本文就到這里，總結(jié)來(lái)說(shuō)，如果發(fā)現(xiàn)題目中存在單調(diào)關(guān)系，就可以嘗試使用二分搜索的思路來(lái)解決。搞清楚單調(diào)性和二分搜索的種類(lèi)，通過(guò)分析和畫(huà)圖，就能夠?qū)懗鲎罱K的代碼。

責(zé)任編輯：haq