Go: LeetCode简单题，简单做(sort.Search)

前言

正值端午佳节，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.通常用来在有序列表中进行过滤，也可以判断某个元素是否存在