前言
二分查找算法作為一種常見的查找方法戏蔑，將原本是線性時(shí)間提升到了對(duì)數(shù)時(shí)間范圍，大大縮短了搜索時(shí)間年鸳，具有很大的應(yīng)用場(chǎng)景省撑，而在 LeetCode 中赌蔑，要運(yùn)用二分搜索法來解的題目也有很多，但是實(shí)際上二分查找法的查找目標(biāo)有很多種竟秫，而且在細(xì)節(jié)寫法也有一些變化娃惯。
問題形式：
二分查找算法充分利用了元素間的次序關(guān)系，采用分治策略鸿摇，可在最壞的情況下用 O(logN) 完成搜索任務(wù)石景。
題目問法大致有這幾種
- 查找和目標(biāo)值完全相等的數(shù)
- 查找區(qū)間的某個(gè)邊界值
- 利用子函數(shù)對(duì)中間值進(jìn)行判斷劈猿，確定查找的方向
- 利用二分思想查找函數(shù)的極大值
解題思路與模板
根據(jù)前面的描述可以看出拙吉，這類問題的核心就是在于確定三要素：搜索區(qū)間，終止條件和折半方向揪荣。
標(biāo)準(zhǔn)二分查找
/** 元素按升序排列筷黔，下同 */
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1; // 無符號(hào)右移，即使前面溢出也能得到正確結(jié)果
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 當(dāng)前元素比目標(biāo)值小仗颈，則收縮左邊界佛舱，查找右半邊
} else if (arr[mid] > target) {
right = mid - 1; // 當(dāng)前元素比目標(biāo)值小，則收縮右邊界挨决，查找左半邊
}
}
return -1; // 未找到
}
Q：為什么 while 循環(huán)的終止條件是 left <= right 请祖？而我看到有的代碼里是 left < right ?
A：兩者都可以使用，但它們代表不同的搜索區(qū)間脖祈，需要配合不同的右側(cè)邊界肆捕。帶個(gè)例子來看，假如我們?cè)?[ 1 , 3 , 5 , 7 , 9 ] [1,3,5,7,9] [1,3,5,7,9] 中搜索元素 3 3 3 的索引位置盖高。我們?cè)诖a里加一些輸出語句來看看吧慎陵。
循環(huán)條件是 left <= right 時(shí)
第 1 次循環(huán)開始：left = 0, right = 4, mid = 2
第 1 次循環(huán)結(jié)束：left = 0, right = 1, mid = 2
第 2 次循環(huán)開始：left = 0, right = 1, mid = 0
第 2 次循環(huán)結(jié)束：left = 1, right = 1, mid = 0
第 3 次循環(huán)開始：left = 1, right = 1, mid = 1
找到了 target = 3 ，索引是 1
結(jié)果正確喻奥。下面我們把 <= 改為 <席纽，其他條件不變
循環(huán)條件是 left < right 時(shí)
第 1 次循環(huán)開始：left = 0, right = 4, mid = 2
第 1 次循環(huán)結(jié)束：left = 0, right = 1, mid = 2
第 2 次循環(huán)開始：left = 0, right = 1, mid = 0
第 2 次循環(huán)結(jié)束：left = 1, right = 1, mid = 0
未找到 target = 3
出現(xiàn)了錯(cuò)誤！我們注意到在第二次循環(huán)結(jié)束時(shí)已經(jīng)有 l e f t = r i g h t 撞蚕，不滿足第三次循環(huán)開始條件了润梯。導(dǎo)致了 m i d mid mid 遺漏了索引 1 的位置。如果我們一定要用left<right 作為循環(huán)條件呢？可以通過修改右側(cè)邊界的方式來實(shí)現(xiàn)纺铭，看下面的代碼抒和。
/** 使用 while (left < right) 時(shí)的正確代碼，注意 right 的取值 */
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length; // 注意這里
while (left < right) { // 改用 "<"
int mid = (left + right) >>> 1;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid; // 注意這里
}
}
return -1;
}
這次我們看到了正確的結(jié)果彤蔽。
循環(huán)條件是 left < right 時(shí)
第 1 次循環(huán)開始：left = 0, right = 5, mid = 2
第 1 次循環(huán)結(jié)束：left = 0, right = 2, mid = 2
第 2 次循環(huán)開始：left = 0, right = 2, mid = 1
找到了 target = 3 摧莽，索引是 1
通過上面的比較不難發(fā)現(xiàn)，當(dāng)使用 l e f t ≤ r i g h t 時(shí)顿痪，相當(dāng)于是在閉區(qū)間 [ l e f t , r i g h t ]進(jìn)行搜索镊辕；而當(dāng)使用left<right 時(shí)，相當(dāng)于是在左閉右開區(qū)間[left,right) 進(jìn)行搜索蚁袭。對(duì)于以上兩種形式征懈，如果你已經(jīng)理解了邊界的概念，記住它們自然不在話下揩悄。
Q：標(biāo)準(zhǔn)算法有什么局限性卖哎？
A：至此，你應(yīng)該已經(jīng)掌握了該算法的所有細(xì)節(jié)删性，以及這樣處理的原因亏娜。但是，這個(gè)算法存在局限性蹬挺。比如說給你數(shù)組 [ 1 , 3 , 3 , 3 , 4 ] [1,3,3,3,4] [1,3,3,3,4]维贺，需要搜索元素 3 3 3 的索引，此算法返回的索引是 2巴帮，沒錯(cuò)溯泣。但是如果我想得到 target 的左側(cè)邊界，即索引 1榕茧，或者我想得到 target 的右側(cè)邊界垃沦，即索引 3，這樣的話此算法是無法處理的用押。然而這樣的需求很常見肢簿。你也許會(huì)說，找到一個(gè) target 索引只恨，然后向左或向右線性搜索不行嗎译仗？可以但是不好，假如有大量的重復(fù)元素官觅，那樣就難以保證二分查找對(duì)數(shù)級(jí)的復(fù)雜度了纵菌。下面我們就來討論邊界的二分查找算法。
模板2：尋找第一個(gè)不小于目標(biāo)值的位置
我們注意到在上面的例子中休涤，要找到元素 3 3 3 的左側(cè)邊界咱圆，相當(dāng)于是要找到第一個(gè)不小于元素 3 3 3 的位置笛辟，我們只需要修改兩處代碼就能實(shí)現(xiàn)。
int lowerBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (arr[mid] == target) {
right = mid; // 注意這里
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid;
}
}
return right; // 注意這里序苏，也可以寫為left, 循環(huán)終止時(shí)它們是相等的
}
Q：為什么這樣能找到左邊界手幢？
A：關(guān)鍵在于對(duì)找到target 后這種情況的處理，我們并沒有直接返回索引值忱详，而是繼續(xù)收縮右邊界令 r i g h t = m i d 围来，最終達(dá)到鎖定左邊界的目的。
Q：為什么沒有返回 -1 的操作匈睁？如果數(shù)組不存在這樣的 target 該怎么辦监透？
A：我們繼續(xù)通過打印輸出結(jié)果來看，假如我們?cè)?[ 0 , 1 , 3 , 3 , 3 , 7 , 8 ] [0,1,3,3,3,7,8] [0,1,3,3,3,7,8] 中搜索元素 3 3 3
開始查找航唆，target = 3
第 1 次循環(huán)開始：left = 0, right = 7, mid = 3
第 1 次循環(huán)結(jié)束：left = 0, right = 3, mid = 3
第 2 次循環(huán)開始：left = 0, right = 3, mid = 1
第 2 次循環(huán)結(jié)束：left = 2, right = 3, mid = 1
第 3 次循環(huán)開始：left = 2, right = 3, mid = 2
第 3 次循環(huán)結(jié)束：left = 2, right = 2, mid = 2
結(jié)束查找胀蛮，索引是 2
結(jié)果是索引 2，也就是第一個(gè) 3 3 3 的位置糯钙，正確粪狼。然后我們來看下搜索元素 4 4 4
開始查找，target = 4
第 1 次循環(huán)開始：left = 0, right = 7, mid = 3
第 1 次循環(huán)結(jié)束：left = 4, right = 7, mid = 3
第 2 次循環(huán)開始：left = 4, right = 7, mid = 5
第 2 次循環(huán)結(jié)束：left = 4, right = 5, mid = 5
第 3 次循環(huán)開始：left = 4, right = 5, mid = 4
第 3 次循環(huán)結(jié)束：left = 5, right = 5, mid = 4
結(jié)束查找任岸，索引是 5
結(jié)果是索引 5再榄，也就是元素 7 7 7 的位置。不難看出我們找到了不小于目標(biāo)值的第一個(gè)位置演闭。實(shí)際上在 C++ 標(biāo)準(zhǔn)庫中有專門的函數(shù) lower_bound不跟，替我們實(shí)現(xiàn)了同樣的功能。此外米碰，該類問題還可以變形為尋找最后一個(gè)小于目標(biāo)值的位置。我們只需要在返回結(jié)果那里繼續(xù)左移一步购城，改為 return right - 1 就可以了吕座。
模板3：尋找第一個(gè)大于目標(biāo)值的位置
有了上面的分析，那么這里就很容易理解了瘪板。對(duì)于這種情況吴趴，我們需要不斷收縮左側(cè)邊界，來看代碼侮攀。
int upperBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (arr[mid] == target) {
left = mid + 1; // 注意這里
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid;
}
}
return right; // 注意這里锣枝，也可以寫為left, 循環(huán)終止時(shí)它們是相等的
}
再來看下輸出結(jié)果吧，我們?nèi)匀辉?[ 0 , 1 , 3 , 3 , 3 , 7 , 8 ] [0,1,3,3,3,7,8] [0,1,3,3,3,7,8] 中搜索元素 3 3 3
開始查找兰英， target = 3
第 1 次循環(huán)開始：left = 0, right = 7, mid = 3
第 1 次循環(huán)結(jié)束：left = 4, right = 7, mid = 3
第 2 次循環(huán)開始：left = 4, right = 7, mid = 5
第 2 次循環(huán)結(jié)束：left = 4, right = 5, mid = 5
第 3 次循環(huán)開始：left = 4, right = 5, mid = 4
第 3 次循環(huán)結(jié)束：left = 5, right = 5, mid = 4
找到了撇叁，索引是 5
找到了第一個(gè)大于 3 3 3 的元素 7 7 7 了！同樣在 C++ 標(biāo)準(zhǔn)庫中有專門的函數(shù) upper_bound 實(shí)現(xiàn)了該功能畦贸。然后你可能會(huì)問陨闹，那我們要找最后一個(gè) 3 3 3 的位置（即右邊界）該怎么辦楞捂？非常簡單，只需要在返回值那里左移一步就行了趋厉，改為 return right - 1寨闹。
具體問題
搜索二維矩陣
編寫一個(gè)高效的算法來判斷 m x n 矩陣中，是否存在一個(gè)目標(biāo)值君账。該矩陣具有如下特性：
- 每行中的整數(shù)從左到右按升序排列繁堡。
- 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。
示例
輸入：
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
輸出:：true
解題思路
注意題目中的關(guān)鍵字高效乡数，升序帖蔓，并且每行第一個(gè)整數(shù)大于前一行最后一個(gè)整數(shù)。那么假設(shè)我們把矩陣逐行排列拉成一條線瞳脓，不難看出其實(shí)它就變成了一個(gè)升序的數(shù)組塑娇。題目也就變成了在升序數(shù)組中找一個(gè)目標(biāo)值，說明就能愉快地二分查找了劫侧。我們可以通過一些簡單的坐標(biāo)計(jì)算來把矩陣模擬成一個(gè)數(shù)組埋酬。
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
// 根據(jù)題意不難發(fā)現(xiàn)矩陣內(nèi)第一個(gè)元素一定最小，最后一個(gè)元素一定最大烧栋，如果 target 不在范圍內(nèi)直接返回 false
if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false;
int left = 0, right = m * n;
while (left < right) {
int mid = (left + right) >>> 1;
// 根據(jù)總元素的個(gè)數(shù)計(jì)算矩陣坐標(biāo)
if (matrix[mid / n][mid % n] == target) {
return true;
} else if (matrix[mid / n][mid % n] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return false;
}
找到 K 個(gè)最接近的元素
給定一個(gè)排序好的數(shù)組写妥，兩個(gè)整數(shù) k 和 x，從數(shù)組中找到最靠近 x（兩數(shù)之差最猩笮铡）的 k 個(gè)數(shù)珍特。返回的結(jié)果必須要是按升序排好的。如果有兩個(gè)數(shù)與 x 的差值一樣魔吐，優(yōu)先選擇數(shù)值較小的那個(gè)數(shù)扎筒。
示例
輸入：[1,2,3,4,5], k=4, x=3
輸出：[1,2,3,4]
解題思路
題目中說到有序數(shù)組，并且是連續(xù)區(qū)間酬姆。區(qū)間長度是固定的嗜桌，并且 k k k 的值為正數(shù)，且總是小于給定排序數(shù)組的長度 s i z e size size辞色。因此骨宠，只要我們找到了左邊界的索引，從左邊界開始取 k k k 個(gè)數(shù)相满，就找到了結(jié)果层亿。那么問題就變成了尋找最優(yōu)區(qū)間的左邊界。
首先我們討論左區(qū)間的取值范圍立美，使用具體的例子匿又，就很很清楚地找到規(guī)律：
- 假設(shè)一共有 5 個(gè)數(shù)， [ 0 , 1 , 2 , 3 , 4 ] [0,1,2,3,4] [0,1,2,3,4]悯辙，找 3 個(gè)數(shù)琳省，左邊界最多到元素 2 2 2迎吵。
- 假設(shè)一共有 8 個(gè)數(shù)， [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ] [0,1,2,3,4,5,6,7] [0,1,2,3,4,5,6,7]针贬，找 5 個(gè)數(shù)击费，左邊界最多到元素 3 3 3。
因此桦他，最優(yōu)區(qū)間的左邊界的索引的搜索區(qū)間為 [ 0 , s i z e ? k ] [0, size - k] [0,size?k]蔫巩，這也就是我們二分查找的范圍快压。然后每次取中間值 m i d mid mid 作為左邊界，則待選區(qū)間為 [ m i d , m i d + k ] [mid, mid + k] [mid,mid+k]蔫劣。 這里的二分查找方向比較難想，是通過比較區(qū)間兩端和 x x x 的距離來確定的脉幢，所有情況如下圖歪沃。
- 如果 x x x 離 m i d mid mid 端更近，則說明我們可以進(jìn)一步收縮右邊界沪曙，即 r i g h t = m i d right = mid right=mid萎羔。特別地液走，題目中指出兩個(gè)值和 x x x 的差值一樣時(shí)取較小值（也就是 x x x 恰好位于區(qū)間中間）。那么這種情況下也需要收縮右邊界贾陷。
- 如果 x x x 離 m i d + k mid+k mid+k 端更近缘眶，則說明我們可以進(jìn)一步收縮左邊界昵宇，即 l e f t = m i d + 1 left = mid + 1 left=mid+1
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.length - k;
while (left < right) {
int mid = (left + right) >>> 1;
if (x - arr[mid] > arr[mid + k] - x) { // 通過比較區(qū)間端點(diǎn)和 x 的距離確定二分方向
left = mid + 1;
} else {
right = mid;
}
}
List<Integer> list = new ArrayList<>();
for (int i = left; i < left + k; i++) {
list.add(arr[i]);
}
return list;
}
其它二分法的練習(xí)題：
- 尋找兩個(gè)有序數(shù)組的中位數(shù)
- 搜索旋轉(zhuǎn)排序數(shù)組
- 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
- Pow(x, n)
- x 的平方根
- 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
- 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II
- 尋找峰值
- 第一個(gè)錯(cuò)誤的版本
- 尋找重復(fù)數(shù)
- 長度最小的子數(shù)組
- 兩個(gè)數(shù)組的交集
- 兩個(gè)數(shù)組的交集 II
- 有效的完全平方數(shù)
- 猜數(shù)字大小
- 分割數(shù)組的最大值
- 四數(shù)相加 II
- 找到 K 個(gè)最接近的元素
- 二分查找
- 找出第 k 小的距離對(duì)
