介紹
簡(jiǎn)介
條件：數(shù)組有序
作用：查找數(shù)組中的某個(gè)值
算法描述： 搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。
基本模版
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2; //1
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
其中的'...'是一些細(xì)節(jié)的地方，可以根據(jù)之后題目的要求，進(jìn)行求解。
其中需要注意的是，標(biāo)記為1的地方，也就是求解mid值的代碼，當(dāng)然也可以寫成int mid = (left + right) / 2;但是為了防止left + right的值過大導(dǎo)致的內(nèi)存溢出，一般將其寫為int mid = left + (right - left) / 2的形式。
基本的二分搜索
二分查找我們能想到的就是用來搜索一個(gè)值，如果存在，返回其索引，否則返回 -1。
int binarySearch(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)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
下面簡(jiǎn)單介紹其中涉及到的一些細(xì)節(jié)問題：
- while中為什么是
<=而不是<？
總結(jié)來說，就是考慮區(qū)間[left ,right]還是區(qū)間[left, right),詳細(xì)說明如下。
注意到其中的right取值為nums.length - 1,那么為了能夠?qū)?shù)組中的值全部訪問到，right必然需要能夠被訪問到，即當(dāng)前的搜索區(qū)間在[left, right]之間。
那么停止搜索有兩種情況，一種是找到了target值，直接返回mid，還有一種就是不滿足while循環(huán)條件了，也可以理解為當(dāng)前的搜索區(qū)間不存在了。考慮當(dāng)left == right的時(shí)候，此時(shí)區(qū)間可以寫成為[left, left]，區(qū)間里面還是有值的，能夠進(jìn)入while循環(huán)，之后就有三種情況了，一種直接返回，一種是left = left + 1, 還有一種是right = right - 1（因?yàn)橹笆?code>left == right == mid），不過不論是哪一種，都存在left + 1 == right，也就是說最終的終止?fàn)顟B(tài)應(yīng)該是left + 1 == right?；蛘呖梢院?jiǎn)單的通過while(left <= right)分析出終止條件。
為了更明顯的進(jìn)行對(duì)比，可以考慮while(left < right)的終止條件，也就是當(dāng)left == right的時(shí)候，就停止。考慮left == right的情況，此時(shí)區(qū)間為[left, left]，但是此時(shí)的是無(wú)法進(jìn)入循環(huán)的，所以區(qū)間形式寫成[left, left)更為合適。所以此時(shí)，是少考慮一種情況的，那么此時(shí)可以嘗試right = nums.length會(huì)正常運(yùn)行。
更多細(xì)節(jié)方面內(nèi)容可以參考博客
二分查找細(xì)節(jié)詳解
二分查找的坑點(diǎn)與總結(jié)
實(shí)例
01-尋找旋轉(zhuǎn)排序數(shù)組中的最小值
題目描述
已知一個(gè)長(zhǎng)度為 n 的數(shù)組，預(yù)先按照升序排列，經(jīng)由 1 到 n 次 旋轉(zhuǎn) 后，得到輸入數(shù)組。例如，原數(shù)組 nums = [0,1,2,4,5,6,7] 在變化后可能得到：
若旋轉(zhuǎn) 4 次，則可以得到 [4,5,6,7,0,1,2]
若旋轉(zhuǎn) 7 次，則可以得到 [0,1,2,4,5,6,7]
注意，數(shù)組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉(zhuǎn)一次 的結(jié)果為數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
給你一個(gè)元素值 互不相同 的數(shù)組 nums ，它原來是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了多次旋轉(zhuǎn)。請(qǐng)你找出并返回?cái)?shù)組中的最小元素 。
示例1
輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數(shù)組為 [1,2,3,4,5] ，旋轉(zhuǎn) 3 次得到輸入數(shù)組。
示例2
輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數(shù)組為 [0,1,2,4,5,6,7] ，旋轉(zhuǎn) 4 次得到輸入數(shù)組。
題解01 參考
考慮左側(cè)比較
class Solution {
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return -1;
}
int l = 0, r = nums.length - 1;
while(l < r){
if(nums[l] < nums[r]){
return nums[l];
}
int m =l + (r - l) / 2;
if(nums[l] > nums[m]){
r = m;
}else{
l = m + 1;
}
}
return nums[l];
}
}
題解02 參考
考慮右側(cè)比較
class Solution {
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while(l < h){
int m = l + (h - l) / 2;
if(nums[h] > nums[m]){
h = m;
}else if(nums[h] < nums[m]){
l = m + 1;
}
}
return nums[l];
}
}
總結(jié)
二分查找的應(yīng)用條件是有序序列，然而當(dāng)前序列并非是有序的，首先想到的就是序列重排，或者以O(shè)(n)的時(shí)間復(fù)雜度線性查找，但是顯然這道題的目的并非如此。
然后，通過看題解，發(fā)現(xiàn)用的是二分查找，然后各種不明白全都涌上來了【菜雞的悲哀】
- 二分查找用到的是有序序列，為什么當(dāng)前的序列只是局部有序也可以適用呢？
- 二分查找通常有一個(gè)target，用來比較判斷哪個(gè)區(qū)間該縮小，可是該題的target沒有啊
- 二分查找通常返回的是具體的某個(gè)查找對(duì)象，最小值在其中又是如何理解的呢？
在本題中，數(shù)組的旋轉(zhuǎn)是可以看成兩個(gè)有序序列的拼接，那么在搜索的過程中，可能出現(xiàn)的情況是前面有序或者后面有序，例如二分查找搜索局部有序數(shù)組中所描述的例子，
假如：
nums = [4,5,6,7,0,1,2]，則為情況1；
nums = [6,7,0,1,2,4,5]，則為情況2；
此外，本題還可以理解為求解兩個(gè)有序數(shù)組的拼結(jié)點(diǎn)，因?yàn)樽钚≈狄欢ㄊ沁@個(gè)拼結(jié)點(diǎn)所在的地方，如果沒有拼結(jié)點(diǎn)的話，那么就說明這是一個(gè)完整的有序數(shù)組。
因?yàn)槠浔容^可以選擇左端或者右端的值，所以分開進(jìn)行討論一下。
首先，比較nums[left]和nums[mid]的情況。
在比較之前，可以先行對(duì)整個(gè)區(qū)間進(jìn)行判斷，如果當(dāng)前區(qū)間存在nums[left] < nums[right]的情況，那么說明收斂的區(qū)間當(dāng)前有序，那么直接返回收斂的最小值nums[left]即可。而這一步在與左側(cè)進(jìn)行比較的時(shí)候是必須的，因?yàn)橹挥性诖嘶A(chǔ)上，才可以談當(dāng)nums[left] == nums[mid]的情況。
情況一
假設(shè)nums[mid] < nums[left]，說明最小值應(yīng)該在[left, mid]之間，也可以說明拼結(jié)點(diǎn)就在其中，此時(shí)右側(cè)的[mid,right]一定是有序的。此外，考慮到nums[mid]可能為最小值的情況，所以right 被賦值為mid。情況二
假設(shè)nums[mid] > nums[left], 如果當(dāng)前是拼接，說明最小值(mid, right]之間，可以看出此時(shí)[left, mid]中間是連續(xù)的，所以拼結(jié)點(diǎn)必在后一段。那么此時(shí)，nums[mid]肯定不是最小值了，所以可以越過mid，將left賦值為mid + 1。情況三
假設(shè)nums[mid] == nums[left]，雖然說題目有說不包含重復(fù)數(shù)字，這種情況通常是不需要考慮的，但是如果真正運(yùn)行的時(shí)候是通過不了的，例如{2,1}這種情況，mid在開始的時(shí)候與left的值相同，都是0，而且在之后的循環(huán)中，是不滿足上面的任何一種情況的，也就是說l和r的值都是無(wú)法更改的，那么就會(huì)進(jìn)入到死循環(huán)的狀態(tài)了。
綜上，從左端考慮的時(shí)候，因?yàn)閙id求值會(huì)偏向左方，所以考慮mid與left相等的情況，首先在考慮完情況二的第一種情況后，也就是保證了該序列一定不是完整的有序數(shù)組的情況下，可以肯定拼結(jié)點(diǎn)在后面，所以此時(shí)的left賦值mid + 1。
此外，除了上述的情況討論，還有二分查找特有的細(xì)節(jié)難點(diǎn)還需要仔細(xì)考慮一下，如：
1. while循環(huán)是否需要添加等號(hào)?
可以看出while的結(jié)束條件是left == right。按照之前的分析，此時(shí)缺少了一種情況，也就是當(dāng)left == right == mid的時(shí)候，如果假設(shè)此時(shí)存在這種情況，考慮數(shù)組[1]，此時(shí)進(jìn)入狀態(tài)三，也就是left = mid + 1，之后就跳出循環(huán)，返回nums[left]，但是此時(shí)left == 1，超出數(shù)組大小，報(bào)錯(cuò)。
考慮當(dāng)left == right的情況下，也就是將搜索區(qū)間已經(jīng)縮小到了left和right之間，如果繼續(xù)的話，left會(huì)超出區(qū)間范圍，即left == right的時(shí)候已經(jīng)確定了一個(gè)最小值，所以此時(shí)不用再往下繼續(xù)。與之前不同，也是因?yàn)轭}目的目的不同，該題的最終目標(biāo)是求最小值，除了在中途查找到目標(biāo)值之外，就是當(dāng)區(qū)間收斂到只有一個(gè)值的時(shí)候，該值就是目標(biāo)值，而不用像查找具體值那樣，還要看最后left == right的值是否就是最終的target。
2. 返回的值為什么是nums[left]?
因?yàn)樽罱K的終止條件是left == right，所以返回nums[right]也是一樣的
下面就是從端點(diǎn)的右側(cè)進(jìn)行比較，同樣從一下幾種情況進(jìn)行考慮：
情況一
假設(shè)nums[mid] < nums[right]，說明后一段連續(xù)遞增，拼結(jié)點(diǎn)應(yīng)該在[left, mid)之間，所以將right賦值為mid;情況二
假設(shè)nums[mid] > nums[right]，說明前一段連續(xù)遞增，拼結(jié)點(diǎn)應(yīng)該在(mid, right]之間，所以將left賦值為mid + 1;情況三
假設(shè)nums[mid] == nums[right]，說明只可能在left == right == mid的情況下出現(xiàn)，但是在此時(shí)，這么比較是沒有意義的。所以不考慮這種情況。
二分查找一般的比較原則有：
- 如果有目標(biāo)值target，那么直接讓arr[mid] 和 target 比較即可。
- 如果沒有目標(biāo)值，一般可以考慮 端點(diǎn)
二分查找適合的場(chǎng)景：
- 數(shù)組有序和局部有序
局部有序也可以使用二分查找的原因，個(gè)人猜想可能在于其中求解的目的是不同的，此時(shí)并不是去找到一個(gè)具體的target，而是利用二分查找去查找例如最值這類的值，主要的是利用二分查找能夠縮小查找區(qū)間的特性。
02-尋找旋轉(zhuǎn)排序數(shù)組中的最小值2
劍值offer——?？途W(wǎng)
154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II
本題和上題的區(qū)別在于非遞減排序的數(shù)組，所以可能會(huì)有重復(fù)數(shù)據(jù)的情況，比如
- [2, 1, 2, 2, 3, 3, 3]，最小值在[left, mid]中間
- [2, 2, 2, 2, 3, 1, 2], 最小值在[mid, right]中間
所以此時(shí)并不能夠定位到拼結(jié)點(diǎn)是在哪一塊，那么此時(shí)最好的方法就是將right值減一，防止錯(cuò)過最小值的區(qū)間。
class Solution {
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return -1;
}
int left = 0, right = nums.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[left] < nums[right]){
return nums[left];
}
if(nums[right] < nums[mid]){
left = mid + 1;
}else if(nums[right] > nums[mid]){
right = mid;
}else if(nums[right] == nums[mid]){
right = right - 1;
}
}
return nums[left];
}
}
這邊的nums[left] < nums[right]并非是必須的，只是能夠加快判斷速度的作用。因?yàn)樵谙嗟鹊那闆r下具有不確定性。
最后，本文如果有什么思考錯(cuò)誤的地方，歡迎指出！
