二分搜索
- 二分搜索模板
- 二分搜索運用
圖片來源于網(wǎng)絡(luò)
1. 二分搜索模板
二分搜索（二分查找）也稱折半查找（Binary Search），是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。
二分搜索框架如下：
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
分析二分查找的一個技巧是：不要出現(xiàn) else，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現(xiàn)所有細節(jié)。
1.1 基本的二分搜索
/**
* 尋找一個數(shù)（基本的二分搜索）
* <p>
* 搜索一個數(shù)，如果存在，返回其索引，否則返回 -1
* <p>
* 缺陷：針對如 nums = [1,2,2,2,3]，target為 2 時，此算法返回的索引是 2，而無法處理左側(cè)邊界索引1和右側(cè)邊界索引3
* <p>
* 初始化 right = nums.length - 1，決定了「搜索區(qū)間」是 [left, right]
* 決定了 while (left <= right)，同時也決定了 left = mid+1 和 right = mid-1
* <p>
* 只需找到一個 target 的索引即可，當(dāng) nums[mid] == target 時可以立即返回
*/
private int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// [left, right]，終止條件是 left == right + 1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 直接返回
return mid;
} else if (nums[mid] < target) {
// 搜索區(qū)間變?yōu)?[mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// right = ...
right = mid - 1;
}
}
return -1;
}
1.2 尋找左側(cè)邊界的二分搜索
/**
* 尋找左側(cè)邊界的二分搜索
* <p>
* 初始化 right = nums.length，決定了「搜索區(qū)間」是 [left, right)
* 決定了 while (left < right)，同時也決定了 left = mid + 1 和 right = mid
* <p>
* 因為需找到 target 的最左側(cè)索引，所以當(dāng) nums[mid] == target 時不要立即返回
* 而要收緊右側(cè)邊界以鎖定左側(cè)邊界
*/
private int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
// [left, right)，終止的條件是 left == right
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
// left = ...
left = mid + 1;
} else if (nums[mid] > target) {
// right = ...
right = mid;
}
}
return left;
}
當(dāng)然，上面算法也可以使用兩邊都閉的「搜索區(qū)間」來實現(xiàn)：
/**
* 尋找左側(cè)邊界的二分搜索 [left, right]
*/
private int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
// 搜索區(qū)間為 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 別返回，鎖定左側(cè)邊界 (收縮右側(cè)邊界)
right = mid - 1;
} else if (nums[mid] < target) {
// 搜索區(qū)間變?yōu)?[mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索區(qū)間變?yōu)?[left, mid-1]
right = mid - 1;
}
}
// 最后要檢查 left 越界的情況
if (left >= nums.length || nums[left] != target) return -1;
return left;
}
1.3 尋找右側(cè)邊界的二分搜索
/**
* 尋找右側(cè)邊界的二分搜索
* <p>
* 初始化 right = nums.length，決定了「搜索區(qū)間」是 [left, right)
* 決定了 while (left < right)，同時也決定了 left = mid + 1 和 right = mid
* <p>
* 需找到 target 的最右側(cè)索引，當(dāng) nums[mid] == target 時不要立即返回
* 而要收緊左側(cè)邊界以鎖定右側(cè)邊界
* <p>
* 又因為收緊左側(cè)邊界時必須 left = mid + 1，所以最后無論返回 left 還是 right，必須減一
*/
private int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
// [left, right)
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
// 收緊左側(cè)邊界以鎖定右側(cè)邊界
left = mid + 1;
} else if (nums[mid] < target) {
// left = ...
left = mid + 1;
} else if (nums[mid] > target) {
// right = ...
right = mid;
}
}
// return left - 1; // or return right - 1;
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
}
同樣的，上面算法也可以使用兩邊都閉的「搜索區(qū)間」來實現(xiàn)：
/**
* 尋找右側(cè)邊界的二分搜索 [left, right]
*/
private int right_bound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 別返回，鎖定右側(cè)邊界 (收縮左側(cè)邊界)
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 最后要檢查 right 越界的情況
if (right < 0 || nums[right] != target) return -1;
return right;
}
小結(jié)：
- 分析二分查找代碼時，不要出現(xiàn)
else，全部展開成else if方便理解。 - 注意「搜索區(qū)間」和
while的終止條件，如果存在漏掉的元素，記得在最后檢查。 - 如需定義左閉右開的「搜索區(qū)間」搜索左右邊界，只要在
nums[mid] == target時做修改即可，搜索右側(cè)時需要減一。 - 如果將「搜索區(qū)間」全都統(tǒng)一成兩端都閉，只要稍改
nums[mid] == target條件處的代碼和返回的邏輯即可。
2. 二分搜索的運用
二分搜索除了在有序數(shù)組中搜索給定的某個目標值的索引，當(dāng)搜索空間有序的時候，也可以過二分搜索「剪枝」，大幅提升效率。
2.1 愛吃香蕉的珂珂
力扣 875 題如下：
愛吃香蕉的珂珂
上面題目用暴力解法比較容易寫出如下代碼：
/**
* 暴力解法
* <p>
* Koko 每小時最多吃一堆香蕉，如果吃不下的話留到下一小時再吃；
* 如果吃完了這一堆還有胃口，也只會等到下一小時才會吃下一堆。
* 在這個條件下，確定珂珂吃香蕉的最小速度（根/小時）
* <p>
* 算法要求的「H小時內(nèi)吃完香蕉的最小速度」speed，顯然最少為 1，最大為 max(piles)
*/
private int minEatingSpeed(int[] piles, int H) {
// piles 數(shù)組的最大值
int max = getMax(piles);
for (int speed = 1; speed < max; speed++) {
// 以 speed 是否能在 H 小時內(nèi)吃完香蕉
if (canFinish(piles, speed, H)) {
return speed;
}
}
return max;
}
值得注意的是，上面的 for 循環(huán)是在連續(xù)的空間線性搜索，也就是二分查找可以發(fā)揮作用的標志。
用尋找左側(cè)邊界的二分搜索來代替線性搜索，如下：
/**
* 借助二分查找技巧，算法的時間復(fù)雜度為 O(NlogN)
*/
int minEatingSpeed(int[] piles, int H) {
int left = 1;
int right = getMax(piles) + 1;
// 套用 尋找左側(cè)邊界的二分搜索 框架
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/**
* 在規(guī)定時間內(nèi)是否能吃完香蕉
*
* @param piles 香蕉數(shù)量
* @param speed 吃香蕉速度
* @param H 規(guī)定時間
*/
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
/**
* 吃一堆香蕉的時間
*
* @param n 一堆香蕉的個數(shù)
* @param speed 吃香蕉的速度
*/
int timeOf(int n, int speed) {
return (n / speed) + ((n % speed > 0) ? 1 : 0);
}
/**
* 數(shù)組最大值
*/
int getMax(int[] piles) {
int max = 0;
for (int n : piles) {
max = Math.max(n, max);
}
return max;
}
2.2 包裹運輸問題
力扣 1011 題如下：
在 D 天內(nèi)送達包裹的能力
上面題目本質(zhì)上和珂珂吃香蕉的問題是一樣的，需要確定運輸?shù)?strong>最小載重，假設(shè)其最小值和最大值分別為 max(weights) 和 sum(weights)，用尋找左側(cè)邊界的二分搜索優(yōu)化線性搜索如下：
/**
* 最小載重
*/
int shipWithDays(int[] weights, int D) {
// 載重可能的最小值
int left = getMax(weights);
// 載重可能的最大值 + 1
int right = getSum(weights) + 1;
// 套用 尋找左側(cè)邊界的二分搜索 框架
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, mid, D)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/**
* 若載重為 cap，是否能在 D 天內(nèi)運完貨物？
*/
boolean canFinish(int[] weights, int cap, int D) {
int i = 0;
for (int day = 0; day < D; day++) {
int maxCap = cap;
while ((maxCap -= weights[i]) >= 0) {
i++;
if (i == weights.length) {
return true;
}
}
}
return false;
}
/**
* 數(shù)組最大值
*/
int getMax(int[] piles) {
int max = 0;
for (int n : piles) {
max = Math.max(n, max);
}
return max;
}
/**
* 數(shù)組和
*/
int getSum(int[] weights) {
int sum = 0;
for (int n : weights) {
sum += n;
}
return sum;
}
2.3 分割數(shù)組的最大值
力扣 410 題如下：
分割數(shù)組的最大值
上面題目是固定了 m 的值，讓我們確定一個最大子數(shù)組和；那可以反過來，限制一個最大子數(shù)組的和 max，來反推最大子數(shù)組的和為 max 時，至少可以將 nums 分割成幾個子數(shù)組。定義函數(shù)如下：
/**
* 在每個子數(shù)組和不超過 max 的條件下，計算 nums 至少可以分割成幾個子數(shù)組
*
* 如 nums = [7,2,5,10]，若 max = 10，則split函數(shù)返回 3，
* 即 nums 數(shù)組最少能分割成三個子數(shù)組，分別是[7,2],[5],[10]
*/
int split(int[] nums, int max);
若能找到一個最小的 max 值，滿足上述函數(shù) split(nums, max) 的結(jié)果和 m 相等，那么這個 max 值不就是符合題意的「最小的最大子數(shù)組的和」嗎？
接下來對 max 進行窮舉，子數(shù)組至少包含一個元素，至多包含整個數(shù)組，那么最大子數(shù)組的和 max 的取值范圍是閉區(qū)間 [max(nums), sum(nums)]，即最大元素值到整個數(shù)組和之間，如下所示：
/**
* 計算最大子數(shù)組的和
*/
int splitArray(int[] nums, int m){
int low = getMax(nums);
int high = getSum(nums);
for (int max = low; max <= high; max++){
// 如果最大子數(shù)組和是 max，至少可以把 nums 分割成 n 個子數(shù)組
int n = split(nums, max);
// 為什么是 <= 不是 == ？
// split 函數(shù)采用了貪心的策略，計算的是 max 限制下至少能夠?qū)?nums 分割成幾個子數(shù)組
if (n <= m){
return max;
}
}
return -1;
}
/**
* 在每個子數(shù)組和不超過 max 的條件下，計算 nums 至少可以分割成幾個子數(shù)組
*
* 如 nums = [7,2,5,10]，若 max = 10，則split函數(shù)返回 3，
* 即 nums 數(shù)組最少能分割成三個子數(shù)組，分別是[7,2],[5],[10]
*/
int split(int[] nums, int max){
// 至少可以分割的子數(shù)組數(shù)量
int count = 1;
// 記錄每個子數(shù)組的元素和
int sum = 0;
for (int i = 0; i< nums.length; i++){
if (sum + nums[i] > max){
// 如果當(dāng)前子數(shù)組和大于 max 限制，則這個子數(shù)組不能再添加元素了
count++;
sum = nums[i];
} else {
// 當(dāng)前子數(shù)組和還沒達到 max 限制，還可以添加元素
sum += nums[i];
}
}
return count;
}
/**
* 數(shù)組最大值
*/
int getMax(int[] nums) {
int max = 0;
for (int n : nums) {
max = Math.max(n, max);
}
return max;
}
/**
* 數(shù)組和
*/
int getSum(int[] nums) {
int sum = 0;
for (int n : nums) {
sum += n;
}
return sum;
}
上面代碼是用暴力解法實現(xiàn)的，由于 split 是單調(diào)函數(shù)，且符合二分查找技巧進行優(yōu)化的標志，因此可用二分搜索進行優(yōu)化。
因為算法返回最小的那個 max，所以用尋找左側(cè)邊界的二分搜索優(yōu)化如下：
/**
* 計算最大子數(shù)組的和
* <p>
* 假設(shè) nums 元素個數(shù)為 N，元素和為 S，則 split 函數(shù)的復(fù)雜度為 O(N)，二分查找的復(fù)雜度為 O(logS)，
* 所以算法的總時間復(fù)雜度為 O(N*logS)
*/
int splitArray(int[] nums, int m) {
int left = getMax(nums);
// 一般搜索區(qū)間是左開右閉的，所以 right 要額外加一
int right = getSum(nums) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 根據(jù)分割子數(shù)組的個數(shù)收縮搜索區(qū)間
int n = split(nums, mid);
if (n == m) {
// 收縮右邊界，達到搜索左邊界的目的
right = mid;
} else if (n < m) {
// 最大子數(shù)組和上限高了，減小一些
right = mid;
} else if (n > m) {
// 最大子數(shù)組和上限低了，增加一些
left = mid + 1;
}
}
return left;
}
int split(int[] nums, int max) {... }
int getMax(int[] nums) {... }
int getSum(int[] nums) {... }
小結(jié)：
二分查找在實際問題中的應(yīng)用，首先思考使用 for 循環(huán)暴力解決問題，觀察代碼是否如下形式：
for (int i = 0; i < n; i++){
if (isOK(i)) return answer;
}
如果是，那么就可以使用二分搜索優(yōu)化搜索空間：如果要求最小值就是搜索左側(cè)邊界的二分，如果要求最大值就用搜索右側(cè)邊界的二分。
參考鏈接：
