二分查找,又名折半查找,其搜索過(guò)程如下:

• 從數(shù)組中間的元素開(kāi)始,如果元素剛好是要查找的元素,則搜索過(guò)程結(jié)束
• 如果搜索元素大于或小于中間元素,則排除掉不符合條件的那一半元素,在剩下的數(shù)組中進(jìn)行查找
• 由于每次需要排除掉一半不符合要求的元素,這需要數(shù)組是已經(jīng)排好序的或者是有規(guī)律可循的

在二分查找中,對(duì)于每一個(gè)反饋,我們能過(guò)濾掉一半的數(shù)據(jù),因此二分查找相對(duì)于普通遍歷是一個(gè)高效的查找算法,其時(shí)間復(fù)雜度為O(logn),雖然二分查找的思想很簡(jiǎn)單,然而二分查找的細(xì)節(jié)可不少,這里根據(jù)力扣的題型給出兩種二分查找的寫(xiě)法

二分查找基礎(chǔ)版

題目鏈接

使用二分查找的方式在一個(gè)升序的數(shù)組中找到指定的值并且返回,其代碼框架如下:

定義left為左指針,right為右指針,搜索的區(qū)域在[left,right]中
搜索目標(biāo)值為targtwhile(left<=right){//得到查找的中點(diǎn)mid=(left+right)/2//對(duì)于升序數(shù)組當(dāng)前值小于目標(biāo)值，目標(biāo)值應(yīng)該在當(dāng)前值的右側(cè)if(mid<target){左指針右移，如今搜索區(qū)域變?yōu)閇mid,right]}else if(mid>target){右指針左移，如今搜索區(qū)域變?yōu)閇left,mid]}else{只剩下等于的情況了，直接返回結(jié)果找到了目標(biāo)值}
}

代碼如下：

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = (right - left) // 2 + leftnum = nums[mid]if num < target:left = mid + 1elif num > target:right = mid - 1else:return midreturn -1

注意，重點(diǎn)來(lái)了！！！注意代碼中的幾個(gè)關(guān)鍵點(diǎn)：

• while循環(huán)中的條件是left<=right，這意味著在搜索不到答案退出循環(huán)時(shí)left=right+1，而在二分查找中我們查找的是[left,right]這個(gè)區(qū)間，這說(shuō)明所有的數(shù)都被搜索到了，記住這一點(diǎn)，以下我們統(tǒng)稱left<=right的這種寫(xiě)法為寫(xiě)法一
• mid=(right-left)//2+left這個(gè)寫(xiě)法其實(shí)與mid=(left+right)/2效果是一致的，這么寫(xiě)的目的是為了防止整形溢出的情況，因?yàn)閘eft+right相加如果大于整形最大值的話會(huì)導(dǎo)致結(jié)果異常
• 在移動(dòng)左右指針時(shí)使用的是right=mid-1和left=mid+1，這是因?yàn)閙id的值已經(jīng)在上一輪循環(huán)中搜索過(guò)了，不需要再進(jìn)行一次搜索

二分查找進(jìn)階版--尋找左右邊界

為了引出二分查找的第二種寫(xiě)法,這里給出一道非力扣題型的二分查找

尋找左側(cè)邊界

例如對(duì)于數(shù)組[1,2,2,2,3],查找目標(biāo)為2,我們需要返回最左邊的2的下標(biāo)1,如果使用寫(xiě)法一我們的代碼看起來(lái)是下面這樣的:

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = (right - left) // 2 + leftnum = nums[mid]if num < target:left = mid + 1elif num > target:right = mid - 1else:right = mid - 1if(left >= len(nums) || nums[left] != target): return -1return left

這段代碼有兩個(gè)注意點(diǎn):

• 由于要找到最左側(cè)的邊界,在else條件里(num=target), 我們不再直接返回結(jié)果,而是繼續(xù)的收縮右邊界,直到right越界或者找到最左邊界坐標(biāo)
• 是不是決定很奇怪,為什么最后返回的是left,而且是對(duì)left做越界判定,記不記得我在之前說(shuō)過(guò)left<=right的退出條件是left=right+1,我們復(fù)盤(pán)一下最后一輪循環(huán)的情況,你就知道為什么最后返回的是left而且也是對(duì)left進(jìn)行越界的判斷了

• 復(fù)盤(pán)最后一輪循環(huán)的過(guò)程,對(duì)于數(shù)組[1,2,2,2,3],target為2,假設(shè)當(dāng)前mid為1,循環(huán)也接近了極限,也就是left=mid=right=1,根據(jù)代碼,在num=target=2的時(shí)候,根據(jù)代碼right=mid-1,那么最后right是否一定不指向正確的結(jié)果1,而left指針還沒(méi)有被移動(dòng),依然指向mid,所以我們最后應(yīng)該返回left
• 再來(lái)看一種情況對(duì)于數(shù)組[1,2,2,2,3]如果我們查找的是數(shù)字4,由于數(shù)組中的數(shù)字都小于target,我們會(huì)不斷的縮小左邊界,直到退出循環(huán)left=right+1,此時(shí)left一定是越界的,因?yàn)閞ight從頭到尾都沒(méi)動(dòng)過(guò),而left=right+1保證了left越界
• 再來(lái)看一種情況對(duì)于數(shù)組[1,2,2,2,3]如果查找的是數(shù)字0,由于數(shù)組中的數(shù)字都大于target,我們會(huì)不斷的縮小右邊界,直到退出循環(huán)left=right+1,由于我們最后判斷的是left指針,即使right指針越界了,left=right+1也能保證left剛好在下標(biāo)0的位置,所以是不需要考慮左側(cè)越界的情況的

講到這里是不是覺(jué)得寫(xiě)法一來(lái)解決這樣的問(wèn)題真的很復(fù)雜,所以我們接下來(lái)要說(shuō)寫(xiě)法二

寫(xiě)法二

使用寫(xiě)法二來(lái)解決左側(cè)邊界問(wèn)題,代碼如下:

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left < right:mid = (right - left) // 2 + leftnum = nums[mid]if num < target:left = mid + 1else:right = midreturn left

注意點(diǎn)如下:

• while循環(huán)結(jié)束的條件是left<right,這說(shuō)明循環(huán)退出的條件是left==right==mid,最后的返回值我們這里返回的是left,其實(shí)返回right也是可以的,因?yàn)檠h(huán)退出的條件是left==mid==right嘛
• 可以看到另一個(gè)不同在于在else條件里我們偏移右指針的時(shí)候?qū)懙氖莚ight=mid,我們合并了num>target和num=target的條件,所以為什么是寫(xiě)成right=mid而不是right=mid-1呢?

left=mid+1和right=mid

• 對(duì)于left=mid+1可以這么理解,mid此時(shí)的值一定不是我們需要的值,所以我們可以直接越過(guò).舉個(gè)例子對(duì)于數(shù)組[1,2,3,4,4,5,5],如果要搜索數(shù)字5,我們第一個(gè)搜索到的數(shù)字mid=(left+right)/2=nums[3]=4,此時(shí)4<target,那么是否一定不是我們需要的結(jié)果,那么我們可以直接越過(guò)
• 對(duì)于right=mid,mid的值可能是我們需要的值,但是在當(dāng)前循環(huán)中我們無(wú)法判斷出來(lái),所以我們進(jìn)行保留,舉個(gè)列子,對(duì)于數(shù)組[1,5,5,5],如果要搜索數(shù)字5,我們第一個(gè)搜索到的數(shù)字mid=nums[1]=5,此時(shí)的5是下標(biāo)為1的5,并且也是最終我們需要找到的最左側(cè)邊界,此時(shí)right=mid這行代碼就能幫助我們把結(jié)果保留了,而后等待left不斷右移知道left==right就能退出循環(huán)返回最終結(jié)果了

尋找右側(cè)邊界

學(xué)會(huì)了尋找左側(cè)邊界,那么右側(cè)邊界是否也很容易理解了,其實(shí)這里有一個(gè)小坑,還需要填一下,這里先給出尋找右側(cè)邊界的代碼

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left < right:mid = (right - left + 1) // 2 + leftnum = nums[mid]if num > target:right = mid - 1else:left =  midreturn right

• 相信你已經(jīng)發(fā)現(xiàn)了,在取mid的時(shí)候我們?cè)诶ㄌ?hào)里加上了一個(gè)1,這是因?yàn)槌绦蛘Z(yǔ)言中除法操作后下標(biāo)向下取整(例如(1+2)/2=1),而在尋找右側(cè)邊界的過(guò)程中,這個(gè)操作會(huì)導(dǎo)致死循環(huán),永遠(yuǎn)退不出循環(huán),舉個(gè)列子:
• 兩者相除,向下取整,這個(gè)操作是不是說(shuō)明mid在有些情況下會(huì)向左偏向,我們?cè)趯ふ易髠?cè)邊界的時(shí)候,需要它向左偏向因此能退出循環(huán),而在尋找右側(cè)邊界時(shí),需要它向右收縮邊界,此時(shí)是否就和向下取整這個(gè)情況矛盾了,此時(shí)一左一右就會(huì)導(dǎo)致永遠(yuǎn)進(jìn)入死循環(huán)了,因此需要mid=(right-left+1)//2+left這個(gè)操作來(lái)打破這個(gè)死循環(huán)

總結(jié)

這里很重要哦,如果理解了這里,就離徹底理解二分寫(xiě)法不遠(yuǎn)了

• 寫(xiě)法一適合用于在[left,right]這個(gè)范圍內(nèi)找到值,例如最基礎(chǔ)的二分寫(xiě)法,這種寫(xiě)法需要判斷最后返回的是left還是right,要分析最后一次循環(huán)后造成的結(jié)果
• 寫(xiě)法二適合用于在[left,right]這個(gè)區(qū)間內(nèi)排除值,然后在left=right=mid的時(shí)候找到最后的答案,因此寫(xiě)法二的if條件里寫(xiě)的是target值一定不存在的情況
• 在寫(xiě)法二中如果else條件里是left=mid這個(gè)條件(趨向是收縮左邊界和向下取整相反),需要修改mid為(right-left+1)//2+left來(lái)避免死循環(huán)情況的出現(xiàn)

二分搜索代碼很簡(jiǎn)單,但細(xì)節(jié)是魔鬼,如果覺(jué)得自己理解了可以使用寫(xiě)法二做做這一題,題目鏈接