Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（十）：二分查找的變形版本
日常開發(fā)過程中，除了我們上篇講到的正常的二分查找，還有很多二分查找的變形版本，今天開始，我們就來給大家一一介紹這些變形版本。
從給定序列中查找第一個(gè)匹配元素
符合標(biāo)準(zhǔn)的二分查找條件的序列一般是比較理想的情況，如果要查找的元素在序列中有多個(gè)怎么辦？所以我們要給大家介紹的第一個(gè)常見的變形版本，就是在一個(gè)給定排序序列中查找第一個(gè)等于給定值的元素。在繼續(xù)往下看之前，你不妨借機(jī)先思考一下要怎么實(shí)現(xiàn)。
其實(shí)關(guān)鍵節(jié)點(diǎn)就在于在序列中找到值等于待查找元素值時(shí)的處理。如果此時(shí) mid 位置已經(jīng)到了序列的最左邊，不能再往左了，或者序列中索引小于 mid 的上一個(gè)元素值不等于待查找元素值，那么此時(shí) mid 就是第一個(gè)等于待查找元素值的位置；否則還要繼續(xù)往前找。
對應(yīng)的 Go 實(shí)現(xiàn)代碼如下，其他地方都一樣，就是 num == nums[mid] 時(shí)的處理邏輯變了：
package main
import (
"fmt"
)
// 二分查找變形版本1：查找第一個(gè)值等于給定值的元素
func binarySearchV1(nums []int, num, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if num < nums[mid] {
return binarySearchV1(nums, num, low, mid - 1)
} else if num > nums[mid] {
return binarySearchV1(nums, num, mid + 1, high)
} else {
// 除了需要判斷第一個(gè)與 num 相等的元素索引外，其他和普通二分查找邏輯一致
if mid == 0 || nums[mid-1] != num {
return mid
} else {
return binarySearchV1(nums, num, low, mid - 1)
}
}
}
func main() {
nums := []int{1, 2, 3, 3, 4, 5, 6}
num := 3
index := binarySearchV1(nums, num, 0, len(nums) - 1)
if index != -1 {
fmt.Printf("Find num %d first at index %d\n", num, index)
} else {
fmt.Printf("Num %d not exists in nums\n", num)
}
}
運(yùn)行上述代碼，打印結(jié)果如下：
從給定序列中查找最后一個(gè)匹配元素
既然有第一個(gè)等于給定值的查詢，自然就有最后一個(gè)等于給定值的查詢，這就是二分查找的第二個(gè)變形版本：在給定已排序序列中查找最后一個(gè)等于給定值的元素。
實(shí)現(xiàn)邏輯和上面類似，只需要改動(dòng) num == nums[mid] 時(shí)的處理邏輯，只是這時(shí)的條件變成了 mid 位置到了序列的最右邊，不能再往后了，或者索引大于 mid 的后一個(gè)元素值不等于待查找元素，才返回 mid，否則，還要繼續(xù)往后找。
下面我來給出查找最后一個(gè)等于給定值的元素的 Go 實(shí)現(xiàn)代碼：
package main
import "fmt"
// 二分查找變形版本2：查找最后一個(gè)值等于給定值的元素
func binarySearchV2(nums []int, num, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if num < nums[mid] {
return binarySearchV2(nums, num, low, mid - 1)
} else if num > nums[mid] {
return binarySearchV2(nums, num, mid + 1, high)
} else {
// 除了需要判斷最后一個(gè)與 num 相等的元素索引外，其他和普通二分查找邏輯一致
if mid == len(nums) - 1 || nums[mid + 1] != num {
return mid
} else {
return binarySearchV2(nums, num, mid + 1, high)
}
}
}
func main() {
nums := []int{1, 2, 3, 3, 4, 5, 6}
num := 3
index := binarySearchV2(nums, num, 0, len(nums) - 1)
if index != -1 {
fmt.Printf("Find num %d last at index %d\n", num, index)
} else {
fmt.Printf("Num %d not exists in nums\n", num)
}
}
運(yùn)行上述代碼，打印結(jié)果如下：
在給定序列中查找第一個(gè)大于等于給定值的元素
二分查找的第三個(gè)變形版本是：在給定排序序列中查找第一個(gè)大于等于給定值的元素。
有了前面的基礎(chǔ)，來解決這個(gè)問題，是不是很簡單？所不同的是判斷節(jié)點(diǎn)不一樣了，我們之前的需求都是查找等于給定值，現(xiàn)在變成了大于等于給定值，所以我們要在 nums[mid] >= num 這個(gè)判斷條件上做文章，思路還是和之前兩個(gè)變形版本類似，當(dāng) mid 已經(jīng)是最左邊的元素，或者 mid 的前一個(gè)元素值小于給定查詢值，則 mid 對應(yīng)元素即為滿足條件的元素，否則繼續(xù)往前查找。
對應(yīng)的 Go 實(shí)現(xiàn)代碼如下：
package main
import "fmt"
// 二分查找變形版本3：查找第一個(gè)大于等于給定值的元素
func binarySearchV3(nums []int, num, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if num <= nums[mid] {
// 判斷條件變更，找到第一個(gè)大于等于給定值的元素
// 最左側(cè)元素值，或者當(dāng)前 mid 位置前一個(gè)元素值小于給定值
if mid == 0 || nums[mid-1] < num {
return mid
} else {
return binarySearchV3(nums, num, low, mid-1)
}
} else {
return binarySearchV3(nums, num, mid+1, high)
}
}
func main() {
nums := []int{1, 2, 3, 3, 4, 5, 6}
num := 3
index := binarySearchV3(nums, num, 0, len(nums) - 1)
if index != -1 {
fmt.Printf("Find first num greater or equal than %d at index %d\n", num, index)
} else {
fmt.Printf("Num %d not exists in nums\n", num)
}
}
運(yùn)行上述代碼，打印結(jié)果如下：
在給定序列中查找最后一個(gè)小于等于給定值的元素
與之相對的，還有我們最后要討論的一個(gè)二分查找的變形版本：在給定序列中查找最后一個(gè)小于等于給定值的元素。
有了前面幾個(gè)變形版本的鋪墊，相信你自己就可以寫出對應(yīng)的實(shí)現(xiàn)代碼了。這次的判斷節(jié)點(diǎn)變成了 nums[mid] <= num，其中 num 是待查找的元素值，當(dāng) mid 已經(jīng)是最后一個(gè)元素索引，或者 mid 的后一個(gè)元素值大于 num 則當(dāng)前 mid 對應(yīng)元素就是要查找的元素，否則要繼續(xù)往后查找。
對應(yīng)的 Go 實(shí)現(xiàn)代碼如下：
package main
import "fmt"
// 二分查找變形版本4：查找最后一個(gè)小于等于給定值的元素
func binarySearchV4(nums []int, num, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if num >= nums[mid] {
// 判斷條件變更，找到最后一個(gè)小于等于給定值的元素
// 最右側(cè)元素值，或者當(dāng)前 mid 位置后一個(gè)元素值大于給定值
if mid == len(nums) - 1 || nums[mid + 1] > num {
return mid
} else {
return binarySearchV4(nums, num, mid + 1, high)
}
} else {
return binarySearchV4(nums, num, low, mid - 1)
}
}
func main() {
nums:= []int{1, 2, 3, 3, 4, 5, 6}
num := 3
index := binarySearchV4(nums, num, 0, len(nums) - 1)
if index != -1 {
fmt.Printf("Find last num less or equal than %d at index %d\n", num, index)
} else {
fmt.Printf("Num %d not exists in nums\n", num)
}
}
運(yùn)行上述代碼，打印結(jié)果如下：
關(guān)于二分查找及其變形版本，學(xué)院君就簡單介紹到這里，所有教程代碼，可以在 Github 代碼倉庫獲取：nonfu/go-tutorial，接下來，我們將開始介紹常見的字符串匹配算法。
（本文完）
推薦閱讀