前言
二分查找這個(gè)算法相信大家都很熟悉奈懒，但真正在寫代碼的時(shí)候，對(duì)于邊界條件卻很容易出錯(cuò)宪巨，這篇文章帶你分析二分查找的關(guān)鍵細(xì)節(jié)磷杏，看完以后不再出錯(cuò)。
題目
雖然都是二分查找揖铜，但其實(shí)題目可能會(huì)有細(xì)微的差別茴丰。
這里先統(tǒng)一一下題目：給定非嚴(yán)格遞增的列表nums，給定x天吓，找出其中最小值i贿肩，滿足nums[i] >= x。
也就是說龄寞，如果存在多個(gè)x汰规，則返回第一個(gè)的下標(biāo)；如果不存在x物邑，則返回大于x的下標(biāo)溜哮。
代碼
這里展示兩段代碼，看看兩者的差別色解，你認(rèn)為哪個(gè)正確茂嗓，哪個(gè)錯(cuò)誤呢：
代碼1
func find(nums []int, x int) int {
i, j := 0, len(nums)
var m int
for i < j {
m = i + (j-i)/2
if nums[m] >= x {
j = m
} else {
i = m+1
}
}
return i
}
代碼2
func find(nums []int, x int) int {
i, j := 0, len(nums)-1
var m int
for i <= j {
m = i + (j-i)/2
if nums[m] >= x {
j = m-1
} else {
i = m+1
}
}
return i
}
注意兩者的差別：
- 初始賦值不同，一個(gè)是
j = len(nums)科阎，另一個(gè)是j = len(nums)-1 - 循環(huán)條件不同述吸，一個(gè)是
i < j，另一個(gè)是i <= j - j每次的變化不同锣笨，一個(gè)是
j = m蝌矛，另一個(gè)是j = m-1
你覺得哪一種才是正確的呢？
實(shí)際上错英，兩種都是正確的入撒，只不過這兩段代碼中，j永遠(yuǎn)相差了1而已椭岩。這也導(dǎo)致結(jié)束后茅逮，i和j的狀態(tài)不同。代碼1中結(jié)束時(shí)判哥，i == j献雅；而代碼2中結(jié)束時(shí)i = j+1，記得一定要返回i姨伟，不要返回j惩琉。
但兩種不能混用，如果循環(huán)條件是i <= j夺荒，而j的迭代是j = m瞒渠，則可能會(huì)造成死循環(huán)良蒸。
你可能有疑問，為什么j有兩種迭代方式伍玖，而i只有一種嫩痰？能不能每次迭代讓i = m？這當(dāng)然不行窍箍，因?yàn)閕和j本來就不是對(duì)等的串纺，原因就在于m：i <= m < j，所以迭代部分如果改成i = m可能會(huì)陷入死循環(huán)椰棘。
判斷條件抽象
然后你可能要問了纺棺，如果nums數(shù)組不是遞增而是遞減的怎么辦？如果題目改成要找的是第一個(gè)nums[m] > x 的下標(biāo)邪狞，而不是nums[m] >= x怎么辦祷蝌？
其實(shí)我剛開始也會(huì)在邊界條件糾結(jié)很久，條件稍一變化就又要重新思考帆卓，但這歸根結(jié)底還是對(duì)問題思考的不夠透徹巨朦，沒有把問題抽象出來。
實(shí)際上剑令，我們看代碼里糊啡，只有兩個(gè)地方用到了nums，其中一個(gè)是用到其長度吁津，另一個(gè)就是判斷條件棚蓄。也就是說，其實(shí)二分查找根本不需要知道nums數(shù)組本身腺毫，只要知道其長度癣疟，并且能夠判斷是否滿足條件即可挣柬。
于是我們的代碼可以變成這樣：
代碼3
func Search(n int, f func(int) bool) int {
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1)
if !f(h) {
i = h + 1
} else {
j = h
}
}
return i
}
只需要傳入長度和一個(gè)判斷函數(shù)潮酒，就可以找到第一個(gè)滿足條件的值的下標(biāo)。當(dāng)然邪蛔，判斷函數(shù)f是有約束的：如果f(i) == false, f(j) == true急黎，那么必須滿足 i < j。簡(jiǎn)單說就是左邊是false侧到，右邊是true勃教。
顯然，對(duì)于文章開頭描述的題目匠抗，可以這樣去調(diào)用：
代碼4
func SearchInts(a []int, x int) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
實(shí)際上故源，這兩段代碼，正是golang里面官方sort包下面的函數(shù)汞贸。
這樣一抽象绳军，問題也就看得更加透徹了印机，題目再怎么變化，只要修改這個(gè)判斷函數(shù)f就可以了门驾。
總結(jié)
這篇文章主要講了關(guān)于二分查找的兩個(gè)點(diǎn)：
- i每次迭代都是
i = m + 1射赛，而j在兩種實(shí)現(xiàn)里分成兩檔，涉及到3個(gè)地方奶是，別混用就行楣责。 - 函數(shù)要返回i，不要返回j（j不一定錯(cuò)聂沙，但i一定對(duì)）秆麸。
- for循環(huán)中的if判斷條件，根據(jù)題目進(jìn)行修改即可及汉，代碼最終找到的都是“第一個(gè)滿足該條件的下標(biāo)”
好了蛔屹，以后無論遇到二分查找的什么變種，都能順利解決啦豁生！
