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.