2 minutes
Golang equivalent of Python’s bisect_left() and bisect_right()
Today I needed to binary_search
on a sorted list of items in Golang. In Python (which remains my favorite language, btw) it was a simple thing to use the bisect
module. That got me looking for its equivalent in Golang std packages.
I found what I was looking for in the sort
package. It has a function Search
whose signature is like
func Search(n int, f func(int) bool) int
As per the documentation,
Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) = true implies f(i+1) == true.
So I wrote some wrappers using this Search
function to emulate the functionality of bisect_left
and bisect_right
python functions.
func BisectLeft(a []int, v int) int {
return bisectLeftRange(a, v, 0, len(a))
}
func bisectLeftRange(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
})
}
func BisectRight(a []int, v int) int {
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
})
}
Using the above wrappers, the function for binary_search
for a value is:
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
}
}
Thats it!
Ofcourse this is limited to ints and is not generic. But then its not my fault that Golang does not have generics. Then again I could write a wrapper struct and use reflection
to make it generic, but that is left as and exercise to the reader :D
Sample usage is available at the golang playground.