前言
正值端午佳节，LeetCode也很懂。这两天都是简单题，早点做完去包粽子。
故事从一道简单题说起
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-bad-version
简单题，所以重拳出击，简单分析：产品版本号是1到n，如果每个版本都调用一个isBadVersion函数，将结果放入数组中，则为：[false, ..., false, ture, ..., ture]，即我们从左到右找到第一个值为true的下标即为答案，可使用二分法去找第一个满足isBadVersion函数值为true的version。
func firstBadVersion(n int) int {
left, right := 1, n
for ; left < right; {
mid := left + (right-left) / 2
if isBadVersion(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
PASS，查看题解思路一致。然而，再看一下官方的Go版，只用了一行~
func firstBadVersion(n int) int {
return sort.Search(n, func(version int) bool { return isBadVersion(version) })
}
sort.Search是何方神圣
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
Search函数内部通过二分搜索在下标范围[0,n)中去找到最小的下标是函数f(i)为true，将其返回。要注意，如果下标范围内不存在满足条件的小标，函数返回n。
例：
package main
import (
"fmt"
"sort"
)
func main() {
a := []int{1, 2, 3, 4, 5}
i := sort.Search(len(a), func(i int) bool { return a[i] >= 3 }) // 闭包
fmt.Println(i) // 2
// 寻找某个值
fmt.Println(FindX(a, 4))
fmt.Println(FindX(a, 100))
}
func FindX(sortedA []int, x int) int {
i := sort.Search(len(sortedA), func(i int) bool { return sortedA[i] >= x })
if i < len(sortedA) && sortedA[i] == x {
return i
}
return -1
}
sort.Search总结
1.访问的下标范围： [0,n)
2.如果不存在满足调节，函数返回n
3.通常用来在有序列表中进行过滤，也可以判断某个元素是否存在