# Go - 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
}``````

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

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

``````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
}``````