柚子快報激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 算法——二分查找

http://yzkb.51969.com/

前言：本篇文章繼續(xù)分享一種新的算法——二分查找。

一.二分查找

給定一個?n?個元素有序的（升序）整型數(shù)組?nums?和一個目標(biāo)值?target??，寫一個函數(shù)搜索?nums?中的?target，如果目標(biāo)值存在返回下標(biāo)，否則返回?-1。示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9輸出: 4

解釋: 9 出現(xiàn)在 nums中并且下標(biāo)為 4

示例?2:

輸入: nums = [-1,0,3,5,9,12], target = 2輸出: -1

解釋: 2 不存在 nums 中因此返回 -1

?按照一般的方法去解決上述題目，我們的第一想法肯定是將數(shù)組從頭到尾遍歷一遍，每個值都跟target進(jìn)行一次比較，從而判斷其是否存在于數(shù)組中。

此方法雖然簡單，但是在最差的情況下，需要進(jìn)行n次循環(huán)，即時間復(fù)雜度為O(N)，如果說在數(shù)據(jù)量很大的前提下，這樣做的速度反而是非常慢的。

但是有了數(shù)組已經(jīng)有序（升序）的前提，所以為了降低時間復(fù)雜度，引出二分查找的概念：

取一組數(shù)據(jù)的中間值與target進(jìn)行比較，如果相等，就直接返回；

如果中間值比target小，那么數(shù)組中的目標(biāo)值就一定在中間值的右邊；

如果中間值比target大，那么數(shù)組中的目標(biāo)值就一定在中間值的左邊；

通過中間值的方法，不斷將數(shù)組拆分成兩半，便可以使其中一半不滿足條件的數(shù)據(jù)直接舍棄，無需在進(jìn)行判斷，如此以來的時間復(fù)雜度變?yōu)镺(logN)。

下面來看具體代碼：

int search(vector& nums, int target) {

int left = 0,right = nums.size() - 1;

while(left <= right)

{

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

if(nums[midnum] == target)

{

return midnum;

}

else if(nums[midnum] > target)

right = midnum - 1;

else

left = midnum + 1;

}

return -1;

}

二分查找，需要定義兩個指針left和right，分別管理要處理的數(shù)據(jù)的兩端，起始時為整個數(shù)組的兩端。?

隨后我們需要得出中間值，求中間值有一個細(xì)節(jié)，如果我們使用(right +?left) / 2的方式去求算中間值，那么當(dāng)left和right均接近于INT_MAX時，就會發(fā)生數(shù)據(jù)越界，所以我們采用上述代碼的方式更加穩(wěn)妥。

隨后進(jìn)行比較，當(dāng)中間值和target相等時，遍返回中間值下標(biāo)；如果中間值比target大，則說明目標(biāo)值在中間值的左邊，此時更新right，反之則更新left，取半查找。

直到找到數(shù)據(jù)，或者left > right，即數(shù)組中不存在target時，循環(huán)方可結(jié)束。

值得注意的是，二分查找并不局限于有序的數(shù)組，凡是能夠通過某種規(guī)律將數(shù)據(jù)不斷分成兩半的，均可使用二分查找算法。?

二.x的平方根

給定一個非負(fù)整數(shù)?x?，計算并返回?x?的平方根，即實現(xiàn)?int sqrt(int x)?函數(shù)。

正數(shù)的平方根有兩個，只輸出其中的正數(shù)平方根。

如果平方根不是整數(shù)，輸出只保留整數(shù)的部分，小數(shù)部分將被舍去。

示例 1:

輸入: x = 4

輸出: 2

示例 2:

輸入: x = 8

輸出: 2

解釋: 8 的平方根是 2.82842...，由于小數(shù)部分將被舍去，所以返回 2

本題也是一道相對簡單的題，因為我們無法使用平方根函數(shù)直接解題，所以想要得到一個數(shù)的平方根，我們必須從1開始，算每個數(shù)的平方，直至算到x的平方，判斷是否有一個數(shù)的平方為x。

這其實和從一個升序數(shù)組中找一個值是一樣的，所以本題為了降低時間復(fù)雜度，我們需要采用二分查找的算法：1~x的中點值的平方是否為x作為判斷二分條件，隨后比較大小進(jìn)行二分。

int mySqrt(int x) {

if(x == 0)

return 0;

int left = 1, right = x;

while(left < right)

{

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

long long sum = mid * mid;

if(sum > x)

right = mid - 1;

else

left = mid;

}

return left;

}

但是本題有一個特殊情況，因為一個非負(fù)整數(shù)的平方根不一定也是一個整數(shù)，所以我們要取其取余后的整數(shù)部分，也就是說實際要求的整數(shù)比其平方根要小。

所以在進(jìn)行區(qū)間截取時，我們需要進(jìn)行改動，?因為結(jié)果小于等于目標(biāo)值都有可能，所以我們需要將<=的情況放在一起判斷。并且當(dāng)left變動時，不能再取mid+1，因為有可能mid正好就是那個取余后的整數(shù)。

同樣，我們求中間節(jié)點的方法也需要進(jìn)行優(yōu)化：

實際上除了第一個題目中：left + (right - left) / 2這個求中的的方法外，還有一種方法：

left + (right - left + 1) / 2

那么多的這個＋1，會有什么影響呢？？？?

首先，當(dāng)從left到right有奇數(shù)個數(shù)據(jù)時，使用這兩種方法，所求mid均為中間值。

但是當(dāng)從left到right有偶數(shù)個數(shù)據(jù)時，前者所求數(shù)據(jù)為中間值的左邊，而后者則為中間值的右邊。

這又會產(chǎn)生什么影響？？?

當(dāng)我們要判斷的數(shù)據(jù)只剩兩個時，如果采用?left + (right - left) / 2的方式求中點，當(dāng)遇到判斷結(jié)果要讓left =?mid時，left就會一直等于mid，永遠(yuǎn)不可能大于等于right，這樣就會造成死循環(huán)。

同理，如果采用?left + (right - left + 1) / 2的方式求中點，當(dāng)遇到判斷結(jié)果要讓right?=?mid時，同樣會造成死循環(huán)。

所以當(dāng)出現(xiàn)該情況時，我們只需將上述兩種求中點的方法進(jìn)行交換即可避免死循環(huán)。

三.山峰數(shù)組的峰值索引

符合下列屬性的數(shù)組?arr?稱為?山峰數(shù)組（山脈數(shù)組）?：

arr.length >= 3存在?i（0 < i?< arr.length - 1）使得：

arr[0] < arr[1] < ... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1]

給定由整數(shù)組成的山峰數(shù)組?arr?，返回任何滿足?arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]?的下標(biāo)?i?，即山峰頂部。

示例 1：

輸入：arr = [0,1,0]

輸出：1

示例 2：

輸入：arr = [1,3,5,4,2]

輸出：2

題目還是很容易理解的，就是在數(shù)組中找到最大的一個數(shù)，并返回其下標(biāo)，該數(shù)字大于其左邊的數(shù)單調(diào)遞增，右邊的數(shù)單調(diào)遞減。

?我們可以通過直接遍歷數(shù)組的方法去找這個數(shù)，當(dāng)某數(shù)字比它的后一個數(shù)大時，即為答案。但是如果該數(shù)字為最后一個數(shù)，那我們就需要遍歷整個數(shù)組，時間復(fù)雜度為O(N)。

所以為了優(yōu)化時間復(fù)雜度，雖然這道題不是一個有序的數(shù)組，但我們依然可以采用二分查找。

在該數(shù)組中，某個數(shù)不是比它的前一個數(shù)大，就是比它的前一個數(shù)小，所以我們可以依此為判斷條件：

int peakIndexInMountainArray(vector& arr) {

int left = 0,right = arr.size() - 1;

while(left < right)

{

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

if(arr[mid] < arr[mid - 1])

right = mid - 1;

else

left = mid;

}

return left;

}

如果mid < mid - 1，說明mid在山的右側(cè)，此時山峰在左半?yún)^(qū)，所以right左移；當(dāng)mid >= mid - 1時，?此時mid在山的左半邊，山峰則在右半?yún)^(qū)，left右移，但是因為山峰是最大的數(shù)字，所以此時mid也可能是山峰，所以left的移動不能超過mid。

mid的計算方法則需按照在第二題中分享的方法進(jìn)行考慮。

總結(jié)

二分查找算法適用于能夠?qū)?shù)據(jù)按照某個條件不斷分為兩部分，并逐漸縮短數(shù)據(jù)范圍從而尋找目標(biāo)值的情況，數(shù)據(jù)并非需要嚴(yán)格有序。

關(guān)于二分算法就分享這么多，喜歡本篇文章記得一鍵三連，我們下期再見！

柚子快報激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 算法——二分查找

http://yzkb.51969.com/

推薦鏈接