-
Notifications
You must be signed in to change notification settings - Fork 1
/
slice_binary_search.go
48 lines (42 loc) · 1002 Bytes
/
slice_binary_search.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package slice
import "golang.org/x/exp/constraints"
// BinarySearch 二分法搜索一段已排序的数
func BinarySearch[T constraints.Ordered](sli []T, target T) (from, to int, hit bool) {
from, to = 0, len(sli)
internal.debugf("input slice %v, length %d, target %v", sli, to, target)
if to == 0 {
return 0, 0, false
}
if target < sli[0] {
return 0, 0, false
}
if target > sli[to-1] {
return to, to, false
}
// 二分
for from < to-1 {
half := from + (to-from)/2
n := sli[half]
internal.debugf("from %d, to %d, half %d (%v)", from, to, half, n)
switch {
default:
internal.debugf("Hit index %d (%v)", half, n)
from, to = half, half+1 // causing break
case n < target:
from = half
case n > target:
to = half
}
}
if sli[from] != target {
return from, to, false
}
// 扩展命中的值域
for ; from > 0 && sli[from-1] == target; from-- {
// nothing
}
for ; to < len(sli) && sli[to] == target; to++ {
// nothing
}
return from, to, true
}