二分法是搜索算法中極其典型的方法，其要求輸入序列有序并可隨機訪問。算法思想為
輸入：有序數(shù)組nums，目的數(shù)值target
要求輸出：如果target存在在數(shù)組中，則輸出其index，否則輸出-1
- 將原數(shù)組通過[left,right]兩個索引劃分范圍，初值left=0,right=數(shù)組的最后一個元素
- 當(dāng)left <= right時
- middle = (left + right)/2
- 判斷nums[middle]是不是要查找的target，如果是則返回結(jié)果
- 判斷nums[middle]> target，證明要查找的target在左邊，因此right = middle - 1
- 判斷nums[middle]< target，證明要查找的target在右邊，因此left = middle + 1
- 沒有查找到return -1。
形如下圖：
傳統(tǒng)的二分法代碼如下：
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := (left + right) / 2
if nums[middle] == target {
return middle
} else if nums[middle] > target {
right = middle - 1
} else {
left = middle + 1
}
}
return -1
}
這里要注意兩個問題：
- 上述算法中的第2步中
=的判斷，即for left <= right還是for left < right。 - 上述算法2.2-2.4中的判斷條件以及下一次查找區(qū)間的設(shè)置
- 返回值代表什么意思
for left<= right 中 = 的判斷
首先對于第一個問題，=是否應(yīng)該存在，取決于對于二分查找的初始化定義，例如：
- 如果二分查找遍歷的區(qū)間采用
[left,right]（數(shù)學(xué)中的雙閉區(qū)間）的形式，考慮left==right即=成立的情況，則表示區(qū)間內(nèi)只有單個操作數(shù)，這種情況還是需要處理，否則無法通過其余方式表示這種情況，所以此時=是必須的。 - 如果二分查找遍歷的區(qū)間采用
[left,right)的形式，考慮left==right即=成立的情況，事實證明，這種情況并不應(yīng)該存在，我們無法用[i,i)表示任何一個區(qū)間，所以，這種情況下，=就不是必須的。
判斷條件以及下一次查找區(qū)間的設(shè)置
然后考察對于第二個問題，判斷條件以及下一次查找區(qū)間應(yīng)該如何設(shè)置？
注意：二分查找是一個經(jīng)典的查找算法，其目的是查找到指定的位置或者值，并不僅限于查找到等于target的index這一種情況。
但無論怎樣，二分查找本身有一個固定模式，即二分，就是從middle處將區(qū)間[left,right]分成兩份，然后根據(jù)middle的情況查找（或者更新新的區(qū)間），因此，我們只需要考慮清楚如下三種條件時要怎么處理即可：
- 當(dāng)遍歷到nums[middle] == target時應(yīng)該怎樣處理（新的查找區(qū)間是什么），即當(dāng)前值等于目標值
- 當(dāng)遍歷到nums[middle] > target時應(yīng)該怎樣處理（新的查找區(qū)間是什么），即當(dāng)前值大于目標值
- 當(dāng)遍歷到nums[middle] < target時應(yīng)該怎樣處理（新的查找區(qū)間是什么），即當(dāng)前值小于目標值
討論完上述兩個問題，其實二分法就有了一個固定的框架：
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := (left + right) / 2
if nums[middle] == target {
// 當(dāng)前值等于目標值時，如何處理（新的查找區(qū)間是什么）
} else if nums[middle] > target {
// 當(dāng)前值大于目標值時，如何處理（新的查找區(qū)間是什么）
} else {
// 當(dāng)前值小于目標值時，如何處理（新的查找區(qū)間是什么）
}
}
// 考慮返回值的意義
return
}
返回值的含義
最后我們討論返回值的含義這一話題。在傳統(tǒng)的二分查找中，只有在兩種情況下會返回：
- 查找到目標target，返回查找到的index
- 未查找到目標target，返回-1。（即文章最起始處 步驟3的含義）
這里返回值的含義表示target在nums中的index，該值只會出現(xiàn)在nums[middle]==target這一條件下。然而，剛才提到了二分查找不總是處理等式條件，因此我們總要思考兩種返回值的含義：
- nums[middle]==target，這時return代表的是什么？
- 數(shù)組中不存在target，此時return的是什么，此時left、right代表什么？
這里我們舉一個稍稍復(fù)雜一點的例子對二分查找進行分析。
- 搜索插入位置
- 在排序數(shù)組中查找元素的第一個和最后一個位置
搜索插入位置
題目要求如下：
這個問題要求返回兩種返回值：
- 在數(shù)組中找到目標值，并返回其索引
- 如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置
其中對于情況1，傳統(tǒng)的二分查找算法就可以解決，而情況2，則需要借助于本部分要講解的返回值的含義。
對于傳統(tǒng)的二分法：
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := (left + right) / 2
if nums[middle] == target {
return middle
} else if nums[middle] > target {
right = middle - 1
} else {
left = middle + 1
}
}
return -1
}
如果target能在nums數(shù)組中查找到，必定最終查找到一個[i,i]類型的區(qū)間，即區(qū)間中只有一個數(shù)字，否則區(qū)間就要再次進行二分。例如：如果要在下列數(shù)組中查找4所在的位置，查找過程如下，第三步時，查找區(qū)間為[2,3]，有兩個值，無法確定答案，則需要再次進行一次查找：
target == 4
nums 1 2 3 4
index 0 1 2 3
1 l r
2 l r
3 l r
4 lr
那么最終我們處理的情況必定是對于區(qū)間[left,right]中，其中l(wèi)eft == right，因此middle == left == right，此時nums[middle]和target的關(guān)系。
- nums[middle] > target，則需要從middle左側(cè)繼續(xù)尋找，right = middle - 1，注意此時left = middle，left > right
- nums[middle] < target，則需要從middle右側(cè)繼續(xù)尋找，left = middle + 1，注意此時right = middle，left > right
所以此時，left指向的永遠是大的那個值，right是小的那個值（因為left <= right時，循環(huán)不會終止，循環(huán)終止條件為left > right，根據(jù)數(shù)組的有序性，nums[left] > nums[right]）。
最后，我們考察該題，對于數(shù)組nums，如果目標值不在其中，那么其最終查找到的值只有兩種情況：
- nums[middle] < target，此時nums[middle]應(yīng)該是第一個小于target的值，如果要查找target所在位置，應(yīng)該返回
大于middle的index，即left - nums[middle] > target，此時nums[middle]應(yīng)該是第一個大于target的值，如果要查找target所在位置，應(yīng)該返回
等于middle的index，用target替換middle位置的值，即left
因此，該題的結(jié)果，只需要修改傳統(tǒng)二分查找的最后一行：
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := (left + right) / 2
if nums[middle] == target {
return middle
} else if nums[middle] > target {
right = middle - 1
} else {
left = middle + 1
}
}
return left
}
在排序數(shù)組中查找元素的第一個和最后一個位置
題目要求如下：
注意這里查找的是元素第一次和最后一次出現(xiàn)的位置，這里我們以查找第一次出現(xiàn)的位置舉例，后者同理。
考察我們在判斷條件以及下一次查找區(qū)間的設(shè)置中強調(diào)的，考察二分查找的三種情況：
| 情況 | 分析 | 操作 |
|---|---|---|
| nums[middle] == target時，即當(dāng)前值等于目標值 | 第一次出現(xiàn)的位置可能在當(dāng)前值前面 | right = middle - 1 |
| nums[middle] > target時，即當(dāng)前值大于目標值 | 第一次出現(xiàn)的位置在當(dāng)前值前面 | right = middle - 1 |
| nums[middle] < target時，即當(dāng)前值小于目標值 | 第一次出現(xiàn)的位置在當(dāng)前值后面 | left = middle + 1 |
與之前不同的是當(dāng)nums[middle] == target時，不再有返回值了，那么考慮最后返回值的含義，最終left > right時情況有如下3種：
| 情況 | 分析 | 操作 |
|---|---|---|
| nums[middle] == target | 此時，middle前的值必定<middle，而不是等于（只要等于，考慮上表的情況1，會使right = middle - 1） | return left |
| nums[middle] > target | 此情況不存在，因為如果有這種情況會繼續(xù)使right=middle-1 | 不進行操作 |
| nums[middle] < target | 此時middle必定是target前的第一個元素 | return left |
經(jīng)過上面的分析后，可以清晰的寫出代碼：
l, r := 0, len(nums)-1
for l <= r {
m := (l + r) / 2
if nums[m] >= target {
r = m - 1
} else {
l = m + 1
}
}
result := l
而查找元素出現(xiàn)的最后一個位置，只需要反過來，最后return right即可。代碼如下：
l, r: = 0, len(nums)-1
for l <= r {
m := (l + r) / 2
if nums[m] <= target {
l = m + 1
} else {
r = m - 1
}
}
result := r
總結(jié)
本文詳細分析了二分查找的所有細節(jié)，對于二分查找處理的問題，我們常常需要更加關(guān)注本文討論的后兩個問題：文章來源：http://www.zghlxwxcb.cn/news/detail-689907.html
- 判斷條件以及下一次查找區(qū)間的設(shè)置
- 返回值的含義
最后填充模版即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-689907.html
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := (left + right) / 2
if nums[middle] == target {
// 當(dāng)前值等于目標值時，如何處理（新的查找區(qū)間是什么）
} else if nums[middle] > target {
// 當(dāng)前值大于目標值時，如何處理（新的查找區(qū)間是什么）
} else {
// 當(dāng)前值小于目標值時，如何處理（新的查找區(qū)間是什么）
}
}
// 考慮返回值的意義
return
}
到了這里，關(guān)于Leetcode刷題筆記——二分法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
