Go - sort包

二分法查找

Search函数

找到要查找的数，并且返回下标。如果target不存在也会返回一个数，这个要注意。

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
}

值得学习的地方：

h := int(uint(i+j) >> 1) 

其他写法, 但是明显上面的写法更优：

h := i + (j-i)/2

用法：猜数游戏，每次猜中间的数比target大，是则返回true，否则返回false。然后继续猜。

func search3(nums []int, target int) int {
    return sort.Search(target, func(i int) bool {
        // if false and i = h + 1
        // if true and j = h
        if nums[i] > target { // 前半区间找
            return true
        }
        return false // 后半区间找
    })
}

Find函数

func Find(n int, cmp func(int) int) (i int, found bool) {
    // The invariants here are similar to the ones in Search.
    // Define cmp(-1) > 0 and cmp(n) <= 0
    // Invariant: cmp(i-1) > 0, cmp(j) <= 0
    i, j := 0, n
    for i < j {
        h := int(uint(i+j) >> 1) // avoid overflow when computing h
        // i ≤ h < j
        if cmp(h) > 0 {
            i = h + 1 // preserves cmp(i-1) > 0
        } else {
            j = h // preserves cmp(j) <= 0
        }
    }
    // i == j, cmp(i-1) > 0 and cmp(j) <= 0
    return i, i < n && cmp(i) == 0
}