二分搜索
- 二分搜索模板
- 二分搜索運(yùn)用
1. 二分搜索模板
二分搜索(二分查找)也稱(chēng)折半查找(Binary Search)涤伐,是一種效率較高的查找方法寡壮。但是旅择,折半查找要求線(xiàn)性表必須采用順序存儲(chǔ)結(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 ...;
}
分析二分查找的一個(gè)技巧是:不要出現(xiàn) else盖溺,而是把所有情況用 else if 寫(xiě)清楚,這樣可以清楚地展現(xiàn)所有細(xì)節(jié)铣缠。
1.1 基本的二分搜索
/**
* 尋找一個(gè)數(shù)(基本的二分搜索)
* <p>
* 搜索一個(gè)數(shù)烘嘱,如果存在,返回其索引蝗蛙,否則返回 -1
* <p>
* 缺陷:針對(duì)如 nums = [1,2,2,2,3]拙友,target為 2 時(shí),此算法返回的索引是 2歼郭,而無(wú)法處理左側(cè)邊界索引1和右側(cè)邊界索引3
* <p>
* 初始化 right = nums.length - 1遗契,決定了「搜索區(qū)間」是 [left, right]
* 決定了 while (left <= right),同時(shí)也決定了 left = mid+1 和 right = mid-1
* <p>
* 只需找到一個(gè) target 的索引即可病曾,當(dāng) nums[mid] == target 時(shí)可以立即返回
*/
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)泰涂,同時(shí)也決定了 left = mid + 1 和 right = mid
* <p>
* 因?yàn)樾枵业?target 的最左側(cè)索引鲫竞,所以當(dāng) nums[mid] == target 時(shí)不要立即返回
* 而要收緊右側(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ū)間」來(lái)實(shí)現(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)是牢,同時(shí)也決定了 left = mid + 1 和 right = mid
* <p>
* 需找到 target 的最右側(cè)索引僵井,當(dāng) nums[mid] == target 時(shí)不要立即返回
* 而要收緊左側(cè)邊界以鎖定右側(cè)邊界
* <p>
* 又因?yàn)槭站o左側(cè)邊界時(shí)必須 left = mid + 1,所以最后無(wú)論返回 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ū)間」來(lái)實(shí)現(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é):
- 分析二分查找代碼時(shí)社搅,不要出現(xiàn)
else
驻债,全部展開(kāi)成else if
方便理解。 - 注意「搜索區(qū)間」和
while
的終止條件形葬,如果存在漏掉的元素合呐,記得在最后檢查。 - 如需定義左閉右開(kāi)的「搜索區(qū)間」搜索左右邊界笙以,只要在
nums[mid] == target
時(shí)做修改即可淌实,搜索右側(cè)時(shí)需要減一。 - 如果將「搜索區(qū)間」全都統(tǒng)一成兩端都閉,只要稍改
nums[mid] == target
條件處的代碼和返回的邏輯即可翩伪。
2. 二分搜索的運(yùn)用
二分搜索除了在有序數(shù)組中搜索給定的某個(gè)目標(biāo)值的索引微猖,當(dāng)搜索空間有序的時(shí)候,也可以過(guò)二分搜索「剪枝」缘屹,大幅提升效率凛剥。
2.1 愛(ài)吃香蕉的珂珂
力扣 875 題如下:
上面題目用暴力解法比較容易寫(xiě)出如下代碼:
/**
* 暴力解法
* <p>
* Koko 每小時(shí)最多吃一堆香蕉,如果吃不下的話(huà)留到下一小時(shí)再吃轻姿;
* 如果吃完了這一堆還有胃口犁珠,也只會(huì)等到下一小時(shí)才會(huì)吃下一堆。
* 在這個(gè)條件下互亮,確定珂珂吃香蕉的最小速度(根/小時(shí))
* <p>
* 算法要求的「H小時(shí)內(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 小時(shí)內(nèi)吃完香蕉
if (canFinish(piles, speed, H)) {
return speed;
}
}
return max;
}
值得注意的是豹休,上面的 for
循環(huán)是在連續(xù)的空間線(xiàn)性搜索炊昆,也就是二分查找可以發(fā)揮作用的標(biāo)志。
用尋找左側(cè)邊界的二分搜索來(lái)代替線(xiàn)性搜索威根,如下:
/**
* 借助二分查找技巧凤巨,算法的時(shí)間復(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ī)定時(shí)間內(nèi)是否能吃完香蕉
*
* @param piles 香蕉數(shù)量
* @param speed 吃香蕉速度
* @param H 規(guī)定時(shí)間
*/
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
/**
* 吃一堆香蕉的時(shí)間
*
* @param n 一堆香蕉的個(gè)數(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 包裹運(yùn)輸問(wèn)題
力扣 1011 題如下:
上面題目本質(zhì)上和珂珂吃香蕉的問(wèn)題是一樣的,需要確定運(yùn)輸?shù)?strong>最小載重洛搀,假設(shè)其最小值和最大值分別為 max(weights)
和 sum(weights)
敢茁,用尋找左側(cè)邊界的二分搜索優(yōu)化線(xiàn)性搜索如下:
/**
* 最小載重
*/
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)運(yùn)完貨物留美?
*/
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 題如下:
上面題目是固定了 m
的值彰檬,讓我們確定一個(gè)最大子數(shù)組和;那可以反過(guò)來(lái)谎砾,限制一個(gè)最大子數(shù)組的和 max
逢倍,來(lái)反推最大子數(shù)組的和為 max
時(shí),至少可以將 nums
分割成幾個(gè)子數(shù)組棺榔。定義函數(shù)如下:
/**
* 在每個(gè)子數(shù)組和不超過(guò) max 的條件下瓶堕,計(jì)算 nums 至少可以分割成幾個(gè)子數(shù)組
*
* 如 nums = [7,2,5,10],若 max = 10症歇,則split函數(shù)返回 3,
* 即 nums 數(shù)組最少能分割成三個(gè)子數(shù)組谭梗,分別是[7,2],[5],[10]
*/
int split(int[] nums, int max);
若能找到一個(gè)最小的 max
值忘晤,滿(mǎn)足上述函數(shù) split(nums, max)
的結(jié)果和 m
相等,那么這個(gè) max
值不就是符合題意的「最小的最大子數(shù)組的和」嗎激捏?
接下來(lái)對(duì) max
進(jìn)行窮舉设塔,子數(shù)組至少包含一個(gè)元素,至多包含整個(gè)數(shù)組远舅,那么最大子數(shù)組的和 max
的取值范圍是閉區(qū)間 [max(nums), sum(nums)]
闰蛔,即最大元素值到整個(gè)數(shù)組和之間痕钢,如下所示:
/**
* 計(jì)算最大子數(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 個(gè)子數(shù)組
int n = split(nums, max);
// 為什么是 <= 不是 == 序六?
// split 函數(shù)采用了貪心的策略任连,計(jì)算的是 max 限制下至少能夠?qū)?nums 分割成幾個(gè)子數(shù)組
if (n <= m){
return max;
}
}
return -1;
}
/**
* 在每個(gè)子數(shù)組和不超過(guò) max 的條件下,計(jì)算 nums 至少可以分割成幾個(gè)子數(shù)組
*
* 如 nums = [7,2,5,10]例诀,若 max = 10随抠,則split函數(shù)返回 3,
* 即 nums 數(shù)組最少能分割成三個(gè)子數(shù)組繁涂,分別是[7,2],[5],[10]
*/
int split(int[] nums, int max){
// 至少可以分割的子數(shù)組數(shù)量
int count = 1;
// 記錄每個(gè)子數(shù)組的元素和
int sum = 0;
for (int i = 0; i< nums.length; i++){
if (sum + nums[i] > max){
// 如果當(dāng)前子數(shù)組和大于 max 限制拱她,則這個(gè)子數(shù)組不能再添加元素了
count++;
sum = nums[i];
} else {
// 當(dāng)前子數(shù)組和還沒(méi)達(dá)到 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;
}
上面代碼是用暴力解法實(shí)現(xiàn)的扔罪,由于 split
是單調(diào)函數(shù)秉沼,且符合二分查找技巧進(jìn)行優(yōu)化的標(biāo)志,因此可用二分搜索進(jìn)行優(yōu)化矿酵。
因?yàn)樗惴ǚ祷刈钚〉哪莻€(gè) max
唬复,所以用尋找左側(cè)邊界的二分搜索優(yōu)化如下:
/**
* 計(jì)算最大子數(shù)組的和
* <p>
* 假設(shè) nums 元素個(gè)數(shù)為 N,元素和為 S坏瘩,則 split 函數(shù)的復(fù)雜度為 O(N)盅抚,二分查找的復(fù)雜度為 O(logS),
* 所以算法的總時(shí)間復(fù)雜度為 O(N*logS)
*/
int splitArray(int[] nums, int m) {
int left = getMax(nums);
// 一般搜索區(qū)間是左開(kāi)右閉的倔矾,所以 right 要額外加一
int right = getSum(nums) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 根據(jù)分割子數(shù)組的個(gè)數(shù)收縮搜索區(qū)間
int n = split(nums, mid);
if (n == m) {
// 收縮右邊界妄均,達(dá)到搜索左邊界的目的
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é):
二分查找在實(shí)際問(wèn)題中的應(yīng)用丰包,首先思考使用 for
循環(huán)暴力解決問(wèn)題,觀(guān)察代碼是否如下形式:
for (int i = 0; i < n; i++){
if (isOK(i)) return answer;
}
如果是壤巷,那么就可以使用二分搜索優(yōu)化搜索空間:如果要求最小值就是搜索左側(cè)邊界的二分邑彪,如果要求最大值就用搜索右側(cè)邊界的二分。
參考鏈接: