github gitlab twitter linkedin email
Golang equivalent of Python's bisect_left() and bisect_right()
May 21, 2016
2 minutes read

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.

Back to posts