In Python, we are used to using bisect to search for elements in the List. In Go, sort.Search() can also provide us with the same purpose.
As in Python, the target array is sorted before searching.
1
2
|
arr := []int{9, 2, 1, 3, 6, 4, 5, 5}
sort. Ints(arr)
|
After sorting, we use sort.Search(), the first parameter is the search target, and the second is the function of the search condition.
Here we input slice: [1 2 3 4 5 5 6 9], find the 5 closest to the left, and the program returns the index 4.
1
2
3
|
// func Search(n int, f func(int) bool) int
i := sort.Search(len(arr), func(i int) bool { return arr[i] >= 5 })
fmt.Println(i) // output: 4
|
But in Python’s bisect.left(), you can specify the search range. (bisect. bisect_left(a, x, lo=0, hi=len(a)))
I found on the Internet that enthusiastic netizens implement the function of specifying the range (reference link):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
func BisectLeft(a []int, v int) int {
// Freely adjust the search range
return bisectLeftRange(a, v, 0, len(a))
}
func bisectLeftRange(a []int, v int, lo, hi int) int {
// The search range will be equal to all elements from lo+1 to hi. If you want to directly cover a, you can write it as arr=arr[lo:hi]
s := a[lo:hi]
return sort.Search(len(s), func(i int) bool {
return s[i] >= v
})
}
func BisectRight(a []int, v int) int {
// Freely adjust the search range
return bisectRightRange(a, v, 0, len(a))
}
func bisectRightRange(a []int, v int, lo, hi int) int {
s := a[lo:hi]
return sort.Search(len(s), func(i int) bool {
return s[i] > v
})
}
|
In this way, we only need to call bisect.left() or bisect.right() like Python to specify the search range.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func BinarySearch(a []int, v int) int {
pos := BisectLeft(a, v)
if pos == len(a) {
// the value sought is higher than the
// max value in the slice
return -1
} else if a[pos] != v {
// the value sought is not found
// this is becuase the BisectLeft would return
// the insertion position for the value,
// irrespective of whether this value was found in the
// slice or not
return -1
} else {
// the value is
return pos
}
}
|
Ref: The 3 ways to sort in Go