日常开发过程中，除了我们上篇讲到的正常的二分查找，还有很多二分查找的变形版本，今天开始，我们就来给大家一一介绍这些变形版本。
从给定序列中查找第一个匹配元素
符合标准的二分查找条件的序列一般是比较理想的情况，如果要查找的元素在序列中有多个怎么办？所以我们要给大家介绍的第一个常见的变形版本，就是在一个给定排序序列中查找第一个等于给定值的元素。在继续往下看之前，你不妨借机先思考一下要怎么实现。
midmidmidnum == nums[mid]package main
import (
"fmt"
)
// 二分查找变形版本1：查找第一个值等于给定值的元素
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 {
// 除了需要判断第一个与 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)
}
}
运行上述代码，打印结果如下：
从给定序列中查找最后一个匹配元素
既然有第一个等于给定值的查询，自然就有最后一个等于给定值的查询，这就是二分查找的第二个变形版本：在给定已排序序列中查找最后一个等于给定值的元素。
num == nums[mid]midmidmid下面我来给出查找最后一个等于给定值的元素的 Go 实现代码：
package main
import "fmt"
// 二分查找变形版本2：查找最后一个值等于给定值的元素
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 {
// 除了需要判断最后一个与 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)
}
}
运行上述代码，打印结果如下：
在给定序列中查找第一个大于等于给定值的元素
二分查找的第三个变形版本是：在给定排序序列中查找第一个大于等于给定值的元素。
nums[mid] >= nummidmidmid对应的 Go 实现代码如下：
package main
import "fmt"
// 二分查找变形版本3：查找第一个大于等于给定值的元素
func binarySearchV3(nums []int, num, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if num <= nums[mid] {
// 判断条件变更，找到第一个大于等于给定值的元素
// 最左侧元素值，或者当前 mid 位置前一个元素值小于给定值
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)
}
}
运行上述代码，打印结果如下：
在给定序列中查找最后一个小于等于给定值的元素
与之相对的，还有我们最后要讨论的一个二分查找的变形版本：在给定序列中查找最后一个小于等于给定值的元素。
nums[mid] <= numnummidmidnummid对应的 Go 实现代码如下：
package main
import "fmt"
// 二分查找变形版本4：查找最后一个小于等于给定值的元素
func binarySearchV4(nums []int, num, low, high int) int {
if low > high {
return -1
}
mid := (low + high) / 2
if num >= nums[mid] {
// 判断条件变更，找到最后一个小于等于给定值的元素
// 最右侧元素值，或者当前 mid 位置后一个元素值大于给定值
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)
}
}
运行上述代码，打印结果如下：
关于二分查找及其变形版本，学院君就简单介绍到这里，所有教程代码，可以在 Github 代码仓库获取：nonfu/go-tutorial，接下来，我们将开始介绍常见的字符串匹配算法。
（本文完）