/ golang

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.