記住這兩個(gè)二分模板，秒殺所有二分查找算法題！
本文總結(jié)自 Doocs 開源社區(qū)旗下“leetcode”項(xiàng)目，作者楊立濱。
項(xiàng)目目前 Stars 數(shù)近 7k，將會(huì)持續(xù)更新，歡迎 Star 關(guān)注。
項(xiàng)目地址：https://github.com/doocs/leetcode
二分查找是一種在每次比較之后將查找空間一分為二的算法。當(dāng)我們要處理的問(wèn)題具備單調(diào)性，或者要搜尋序列的邊界時(shí)，應(yīng)該考慮使用二分查找算法。
但是，網(wǎng)上對(duì)于二分查找的描述紛繁復(fù)雜，包括提到二分查找很多的所謂變種寫法，很容易讓讀者摸不清頭腦。
其實(shí)，二分查找的解題套路可以簡(jiǎn)單總結(jié)為以下兩個(gè)模板：
模板 1：
boolean check(int x) {}int search(int left, int right) {while (left < right) {int mid = (left + right) >> 1;if (check(mid)) {right = mid;} else {left = mid + 1;}}return left;}
模板 2：
boolean check(int x) {}int search(int left, int right) {while (left < right) {int mid = (left + right + 1) >> 1;if (check(mid)) {left = mid;} else {right = mid - 1;}}return left;}
我們做二分題目時(shí)，可以按照以下步驟：
1.寫出循環(huán)條件：while (left < right)，注意是 left < right，而非 left <= right；2.循環(huán)體內(nèi)，先無(wú)腦寫出 mid = (left + right) >> 1；3.根據(jù)具體題目，實(shí)現(xiàn) check() 函數(shù)（有時(shí)很簡(jiǎn)單的邏輯，可以不定義函數(shù)），想一下究竟要用 left = mid 還是 right = mid；4.如果 left = mid，那么無(wú)腦寫出 else 語(yǔ)句 right = mid - 1，并且在 mid 計(jì)算時(shí)補(bǔ)充 +1，即 mid = (left + right + 1) >> 1；5.如果 right = mid，那么無(wú)腦寫出 else 語(yǔ)句 left = mid，并且不需要更改 mid 的計(jì)算；6.循環(huán)結(jié)束時(shí)，left 與 right 相等。
注意，這兩個(gè)模板的優(yōu)點(diǎn)是始終保持答案位于二分區(qū)間內(nèi)，二分結(jié)束條件對(duì)應(yīng)的值恰好在答案所處的位置。 對(duì)于可能無(wú)解的情況，只要判斷二分結(jié)束后的 left 或者 right 是否滿足題意即可。
接下來(lái)，我們來(lái)看幾道二分題目，來(lái)實(shí)際應(yīng)用一下這兩個(gè)二分模板。
題目解析
題目 1：第一個(gè)錯(cuò)誤的版本
你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒(méi)有通過(guò)質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。
假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。
你可以通過(guò)調(diào)用 bool isBadVersion(version) 接口來(lái)判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)。實(shí)現(xiàn)一個(gè)函數(shù)來(lái)查找第一個(gè)錯(cuò)誤的版本。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。
示例：
給定 n = 5，并且 version = 4 是第一個(gè)錯(cuò)誤的版本。調(diào)用 isBadVersion(3) -> false調(diào)用 isBadVersion(5) -> true調(diào)用 isBadVersion(4) -> true所以，4 是第一個(gè)錯(cuò)誤的版本。
解法：
此題我們應(yīng)用模板 1 進(jìn)行二分查找，找到第一個(gè) BadVersion。
/* The isBadVersion API is defined in the parent class VersionControl.*/boolean isBadVersion(int version);public class Solution extends VersionControl {public int firstBadVersion(int n) {int left = 1, right = n;while (left < right) {int mid = (left + right) >>> 1;if (isBadVersion(mid)) {right = mid;} else {left = mid + 1;}}return left;}}
題目 2：在排序數(shù)組中查找數(shù)字
統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8輸出: 2
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6輸出: 0
限制：
?0 <= 數(shù)組長(zhǎng)度 <= 50000
解法：
此題我們同時(shí)應(yīng)用模板 1 和模板 2。兩遍二分，分別查找出左邊界和右邊界。
class Solution {public int search(int[] nums, int target) {if (nums.length == 0) {return 0;}// find first positionint left = 0, right = nums.length - 1;while (left < right) {int mid = (left + right) >>> 1;if (nums[mid] >= target) {right = mid;} else {left = mid + 1;}}if (nums[left] != target) {return 0;}int l = left;// find last positionright = nums.length - 1;while (left < right) {int mid = (left + right + 1) >>> 1;if (nums[mid] <= target) {left = mid;} else {right = mid - 1;}}return left - l + 1;}}
題目 3：愛吃香蕉的珂珂
珂珂喜歡吃香蕉。這里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警衛(wèi)已經(jīng)離開了，將在 H 小時(shí)后回來(lái)。
珂珂可以決定她吃香蕉的速度 K （單位：根/小時(shí)）。每個(gè)小時(shí)，她將會(huì)選擇一堆香蕉，從中吃掉 K 根。如果這堆香蕉少于 K 根，她將吃掉這堆的所有香蕉，然后這一小時(shí)內(nèi)不會(huì)再吃更多的香蕉。
珂珂喜歡慢慢吃，但仍然想在警衛(wèi)回來(lái)前吃掉所有的香蕉。
返回她可以在 H 小時(shí)內(nèi)吃掉所有香蕉的最小速度 K（K 為整數(shù)）。
示例 1：
輸入: piles = [3,6,7,11], H = 8輸出: 4
示例 2：
輸入: piles = [30,11,23,4,20], H = 5輸出: 30
示例 3：
輸入: piles = [30,11,23,4,20], H = 6輸出: 23
解法：
注：一般對(duì)于求最值/極值問(wèn)題，可以考慮使用二分枚舉，找到值的邊界點(diǎn)。
對(duì)于本題，我們應(yīng)用模板 1，二分枚舉吃香蕉的速度，返回能在 H 小時(shí)內(nèi)吃完所有香蕉的最小速度即可。
class Solution {public int minEatingSpeed(int[] piles, int h) {int mx = 0;for (int pile : piles) {mx = Math.max(mx, pile);}int left = 1, right = mx;while (left < right) {int mid = (left + right) >>> 1;int s = 0;for (int pile : piles) {s += (pile + mid - 1) / mid;}if (s <= h) {right = mid;} else {left = mid + 1;}}return left;}}
題目 4：在 D 天內(nèi)送達(dá)包裹的能力
傳送帶上的包裹必須在 D 天內(nèi)從一個(gè)港口運(yùn)送到另一個(gè)港口。
傳送帶上的第 i 個(gè)包裹的重量為 weights[i]。每一天，我們都會(huì)按給出重量的順序往傳送帶上裝載包裹。我們裝載的重量不會(huì)超過(guò)船的最大運(yùn)載重量。
返回能在 D 天內(nèi)將傳送帶上的所有包裹送達(dá)的船的最低運(yùn)載能力。
示例 1：
輸入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5輸出：15解釋：船舶最低載重 15 就能夠在 5 天內(nèi)送達(dá)所有包裹，如下所示：第 1 天：1, 2, 3, 4, 5第 2 天：6, 7第 3 天：8第 4 天：9第 5 天：10請(qǐng)注意，貨物必須按照給定的順序裝運(yùn)，因此使用載重能力為 14 的船舶并將包裝分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允許的。
示例 2：
輸入：weights = [3,2,2,4,1,4], D = 3輸出：6解釋：船舶最低載重 6 就能夠在 3 天內(nèi)送達(dá)所有包裹，如下所示：第 1 天：3, 2第 2 天：2, 4第 3 天：1, 4
提示：
?1 <= D <= weights.length <= 50000?1 <= weights[i] <= 500
解法：
注：一般對(duì)于求最值/極值問(wèn)題，可以考慮使用二分枚舉，找到值的邊界點(diǎn)。
對(duì)于本題，我們應(yīng)用模板 1，二分枚舉運(yùn)載能力 capacity，找到能在 D 天內(nèi)送達(dá)的最小運(yùn)載即可。
class Solution {public int shipWithinDays(int[] weights, int days) {int left = 1, right = Integer.MAX_VALUE;while (left < right) {int mid = (left + right) >> 1;if (check(weights, days, mid)) {right = mid;} else {left = mid + 1;}}return left;}private boolean check(int[] weights, int days, int capacity) {int cnt = 1, t = 0;for (int w : weights) {if (w > capacity) {return false;}if (t + w <= capacity) {t += w;} else {t = w;++cnt;}}return cnt <= days;}}
長(zhǎng)按識(shí)別下圖二維碼，關(guān)注公眾號(hào)「Doocs 開源社區(qū)」，第一時(shí)間跟你們分享好玩、實(shí)用的技術(shù)文章與業(yè)內(nèi)最新資訊。