柚子快報(bào)激活碼778899分享：算法【Java】—— 二分查找

http://yzkb.51969.com/

二分查找算法分析

二分查找算法其實(shí)也是對(duì)撞指針的另一種用法，左右兩個(gè)指針?lè)謩e指向數(shù)據(jù)的左右端點(diǎn)，然后雙指針向中間移動(dòng)。

樸素二分查找

上面這道題是樸素的二分查找算法，由于數(shù)據(jù)是有序的，我們可以從中間值入手 如果中間值大于目標(biāo)值說(shuō)明目標(biāo)值位于綠色區(qū)間則需要修改右指針，如果中間值小于目標(biāo)值的那說(shuō)明目標(biāo)值位于藍(lán)色區(qū)間則需要修改左指針，如果相等的話直接返回下標(biāo)即可。

這里的 mid = left + (right - left) / 2 是為了防止溢出，大家應(yīng)該會(huì)這樣寫 mid = (left + right) / 2，但是由于整型數(shù)據(jù)是有范圍的，所以直接加的話可能會(huì)出現(xiàn)溢出現(xiàn)象，為了避免這一現(xiàn)象的出現(xiàn)，我們使用 left + (right - left) / 2，利用減法獲取一半。

補(bǔ)充： mid = left + (right - left) / 2 或者 mid = left + (right - left + 1) / 2 ，在樸素的二分查找算法是一樣的。

class Solution {

public int search(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) {

right = mid - 1;

} else if(nums[mid] < target) {

left = mid + 1;

} else {

return mid;

}

}

return -1;

}

}

左右端點(diǎn)二分查找

非遞減順序排列指的是可以是遞增，也可以存在相同是數(shù)據(jù)，例如：【1，2，3，3，4，4，4，5，5，6，7】

我們要找到 target 的左端點(diǎn)和右端點(diǎn)，并且要求時(shí)間復(fù)雜度是 logN，大概率要使用二分查找算法來(lái)做，那現(xiàn)在我們需要考慮怎么二分，首先target 的左端點(diǎn)就分成大于等于target 這個(gè)區(qū)間和 小于target 這個(gè)區(qū)間，target 的右端點(diǎn)就分成 小于等于 target 這個(gè)區(qū)間和 大于 target 這個(gè)區(qū)間。

算法實(shí)現(xiàn)： 循環(huán)條件：left < right

為什么不加上等于？因?yàn)榧由系扔诘脑挘鶕?jù)上面我們的二分條件可以知道在循環(huán)中我們最后會(huì)讓 left == right，這個(gè)時(shí)候就是二者相遇，并且可能會(huì)出現(xiàn) nums[left] == taregt 又或者不相等，如果是相等的話，就會(huì)卡死在循環(huán)里，所以循環(huán)條件不能加等于

算法內(nèi)部條件細(xì)節(jié)： 左端點(diǎn)： if(nums[mid] >= target) 這個(gè)需要 right = mid ，為什么不能是 right = mid - 1 呢？ 因?yàn)閙id 所對(duì)應(yīng)的數(shù)據(jù)可能就是 target ,如果是那就不能跳過(guò)了，如果不是那就需要跳過(guò)，所以當(dāng) nums[mid] < target 時(shí)，要left = mid + 1;

右端點(diǎn)也是和上面類似的，if(nums[mid] >= target)這個(gè)條件出現(xiàn)的時(shí)候，說(shuō)明 mid 可能對(duì)應(yīng)的就是target , 所以不能跳過(guò)，left = mid; 否則就是 nums[mid] > target，就需要right = mid - 1

mid 的處理： mid = left + (right - left) / 2 或者 mid = left + (right - left + 1) / 2 在這里就是不一樣的，我們要根據(jù)實(shí)際情況分析，如果是查找左端點(diǎn)，就要使用 mid = left + (right - left) / 2，right 就會(huì)移動(dòng)到 left ，否則 right 就不會(huì)移動(dòng)，這時(shí)候就是死亡循環(huán)了，右端點(diǎn)也是同理可得的。

本題細(xì)節(jié)處理： 如果數(shù)組長(zhǎng)度為零，需要單獨(dú)討論，避免數(shù)組越界訪問(wèn)。 在第一個(gè)二分左端點(diǎn)的時(shí)候，需要判斷此時(shí)的left 對(duì)應(yīng)的數(shù)據(jù)是不是 target ，如果不是，說(shuō)明不存在target ，直接返回答案，如果是，則要修改答案數(shù)組，既然存在target ，就是可以進(jìn)行右端點(diǎn)的查找，并且此時(shí)一定存在右端點(diǎn)

class Solution {

public int[] searchRange(int[] nums, int target) {

int[] ans = {-1,-1};

if(nums.length == 0) {

return ans;

}

int left = 0;

int right = nums.length - 1;

//二分左端點(diǎn)

while(left < right) {

int mid = left + (right - left) / 2;

if(nums[mid] >= target) {

right = mid;

} else {

left = mid + 1;

}

}

if(nums[left] != target) {

return ans;

}

ans[0] = left;

right = nums.length - 1;

//二分右端點(diǎn)

while(left < right) {

int mid = left + (right - left + 1) / 2;

if(nums[mid] <= target) {

left = mid;

} else {

right = mid - 1;

}

}

ans[1] = left;

return ans;

}

}

小結(jié)

當(dāng)數(shù)據(jù)具有二段性的時(shí)候，我們可以使用二分查找算法來(lái)查找目標(biāo)的數(shù)據(jù)。

樸素二分算法是最基礎(chǔ)的，一般要使用到二分的算法題基本用到的是左右端點(diǎn)的二分算法思路。

左右端點(diǎn)二查找算法的模板：

while(left < right) {

int mid = ...

if(nums[mid] ... target) {

...

} else {

...

}

}

mid 的取值：可以這樣子記憶，如果判斷條件出現(xiàn) -1 ，說(shuō)明 mid 就要 +1，即 mid = left + (right - left + 1) / 2

實(shí)戰(zhàn)演練

使用二分查找算法的時(shí)候，一定要找到二段性，只要找到了，一切都好辦，剩下的就是套模板。

搜索插入位置

二段性：小于 target ，大于等于 target 最后有三種情況，要么是找到了 target ，直接返回下標(biāo)，如果沒(méi)有找到，這時(shí)候此時(shí)的下標(biāo)對(duì)應(yīng)的數(shù)據(jù)要么大于target 要么小于 target ，如果是大于target 也是直接返回下標(biāo)，因?yàn)槭遣迦?，如果是小于，那就要返回下?biāo)加一。

class Solution {

public int searchInsert(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) {

left = mid + 1;

} else {

right = mid;

}

}

if(nums[right] >= target) {

return right;

}

return right + 1;

}

}

x 的平方根

暴力算法是枚舉所有的數(shù)字，但是這里我們可以使用二分查找算法，當(dāng) 中間值的平方和大于 target ,說(shuō)明中間值和大于中間值的數(shù)據(jù)都是不符合的，如果中間值是小于的話，那就說(shuō)明中間值以及小于中間值的數(shù)據(jù)都是不符合的，符合二段性

這里建議使用左右端點(diǎn)的算法思路，這是萬(wàn)能的，接下來(lái)就是等于放在哪個(gè)條件，這個(gè)交給你們，都是沒(méi)有問(wèn)題的。

最后要注意溢出問(wèn)題，因?yàn)槭峭ㄟ^(guò)平方來(lái)比較，所以很有可能會(huì)出現(xiàn)溢出，這里強(qiáng)制類型轉(zhuǎn)化一下即可。

class Solution {

public int mySqrt(int x) {

int left = 0;

int right = x;

while(left < right) {

int mid = left + (right - left) / 2;

if((long)mid * mid >= x) {

right = mid;

} else if((long)mid * mid < x) {

left = mid + 1;

}

}

if(left * left == x) {

return left;

}

return left - 1;

}

}

山脈數(shù)組的峰頂索引

二段性超明顯，可能大家目前不知道怎么寫代碼，不過(guò)大家對(duì)山脈那可以了如指掌，類似一個(gè)三角形，只要進(jìn)行二分找到峰頂即可。

利用 arr[mid] 前一個(gè)數(shù)據(jù)或者后一個(gè)數(shù)據(jù)進(jìn)行比較就可以了。

最后二段性自然也就出來(lái)了。

class Solution {

public int peakIndexInMountainArray(int[] arr) {

int left = 0;

int right = arr.length - 1;

while(left < right) {

int mid = left + (right - left + 1) / 2;

if(arr[mid] > arr[mid - 1]) {

left = mid;

} else {

right = mid - 1;

}

}

return left;

}

}

尋找峰值

這個(gè)和上面的山脈數(shù)組的峰頂索引一模一樣，這里就交給聰明的大家了。

class Solution {

public int findPeakElement(int[] nums) {

int left = 0;

int right = nums.length - 1;

while(left < right) {

int mid = left + (right - left + 1) / 2;

if(nums[mid] > nums[mid - 1]) {

left = mid;

} else {

right = mid - 1;

}

}

return left;

}

}

尋找旋轉(zhuǎn)排序數(shù)組中的最小值

將軍莫慮，且看此圖：

因?yàn)槭怯行虻臄?shù)組，經(jīng)過(guò)旋轉(zhuǎn)之后，最小值的左邊一定都大于它，最小值的右邊同樣也都大于它，但是有一個(gè)特殊的地方，就是最小值的右區(qū)間的最小值是比有區(qū)間的最大值要大的，左右區(qū)間的最值很好找，就是端點(diǎn)對(duì)應(yīng)的數(shù)值。

二段性： nums[left] > nums[right] 時(shí)，left 要 + 1 ，避免跳過(guò)了最小值，相反則是 nums[left] <= nums[right]，這時(shí)候說(shuō)明left 對(duì)應(yīng)的就是最小的元素，直接返回即可。

class Solution {

public int findMin(int[] nums) {

int left = 0;

int right = nums.length - 1;

while(left < right) {

if(nums[left] > nums[right]) {

left++;

} else {

return nums[left];

}

}

return nums[left];

}

}

點(diǎn)名

這里可以使用暴力美學(xué)，比較簡(jiǎn)單

如果要使用二分查找，就需要利用好數(shù)組自身內(nèi)容和下標(biāo)，如果發(fā)現(xiàn)是缺人的話，下標(biāo)和數(shù)組自身內(nèi)容是不匹配的：

那么二段性也就出來(lái)了，首先 mid == nums[mid] 的話，需要將 left 移動(dòng)到 mid + 1，然后繼續(xù)二分 如果 mid != nums[mid] 的話，需要將 right 移動(dòng)到 mid ，但不能是 mid - 1 ，可能mid 就是答案。 綜上所述，使用的是 左右端點(diǎn)二分查找算法的模板，大家直接套模板即可。

現(xiàn)在討論特殊情況，如果剛好缺的是最后一個(gè)學(xué)號(hào)，這時(shí)候，經(jīng)過(guò)二分查找之后，會(huì)有兩種情況，一種是剛好下標(biāo)等于數(shù)組內(nèi)容，那么缺席的就是 right + 1 這個(gè)學(xué)號(hào)，另一種是下標(biāo)不等于數(shù)組內(nèi)容，這種直接返回下標(biāo)即可。

class Solution {

public int takeAttendance(int[] records) {

int left = 0;

int right = records.length - 1;

while(left < right) {

int mid = left + (right - left) / 2;

if(mid != records[mid]) {

right = mid;

} else {

left = mid + 1;

}

}

if(right == records.length - 1 && records[right] == right) {

return right + 1;

}

return right;

}

}

柚子快報(bào)激活碼778899分享：算法【Java】—— 二分查找

http://yzkb.51969.com/

精彩鏈接