Binary Search in Go

Binary Search

I know, the word binary screams binary tree. But no, binary search doesn’t require a tree at all. It’s usually implemented in an array. In Go, we can simply use a slice to do this.

Note that a binary search can only be performed on a sorted array.

import "cmp"

// Note: s is already sorted

func BinarySearch[S ~[]E, E cmp.Ordered](s S, target E) (index int, found bool) {
    left, right := 0, len(s)    // exclusive right bound

    for left < right {
        mid := left + (right - left) / 2
        // use this as `(left + right) / 2` might overflow
        
        switch cmp.Compare(s[mid], target) {
        case -1:
            left = mid + 1
        case 1:
            right = mid
        case 0:
            return mid, true
        }
    }
    
    return left, false
}

import "cmp"

// Note: s is already sorted

func BinarySearch[S ~[]E, E cmp.Ordered](s S, target E) (index int, found bool) {
    left, right := 0, len(s)    // exclusive right bound

    for left < right {
        mid := left + (right - left) / 2
        // use this as `(left + right) / 2` might overflow
        
        switch cmp.Compare(s[mid], target) {
        case -1:
            left = mid + 1
        case 1:
            right = mid
        case 0:
            return mid, true
        }
    }
    
    return left, false
}

The generic signature [S ~[]E, E cmp.Ordered] means:

• S is a []E which is a slice of E; ~ means this applies to named types that’s exactly []E as well. So this would include something like type MySlice []E.
• E is anything that’s listed in the cmp.Ordered type constraint.

even if the element is not found, i.e. found returns false, left will still be pointing at the index where target would be inserted.

If you insist on using a built-in function to do binary search, you can use slices.BinarySearch:

import "slices"

func main() {
  s := []T{ /* omitted */ }
  t := T{ /* omitted */ }
  
  idx, found := slices.BinarySearch(s, t)
  // it has the same signature as our custom func
}

import "slices"

func main() {
  s := []T{ /* omitted */ }
  t := T{ /* omitted */ }
  
  idx, found := slices.BinarySearch(s, t)
  // it has the same signature as our custom func
}

Binary search achieves $O(log n)$ time complexity and $O(1)$ space complexity.

First-Element-Satisfying Predicate

So instead of finding an exact match by value, this kind of binary search looks for the first element that meets a given predicate.

Of course, all elements are sorted, but depending on the predicate, the first element that asserts true will be after the last one that fails the assertion, like this:

[F, F, F, F, T, T, T]

[F, F, F, F, T, T, T]

For example:

func FirstTrue[S ~[]E, E any](s S, predicate func(E) bool) (index int, found bool) {
    left, right := 0, len(s)

    for left < right {  // first element is found when left == right
        mid := left + (right - left) / 2

        if predicate(s[mid]) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left, left < len(s)  // [F, F, F, F] where no element satisfies the predicate
}

func FirstTrue[S ~[]E, E any](s S, predicate func(E) bool) (index int, found bool) {
    left, right := 0, len(s)

    for left < right {  // first element is found when left == right
        mid := left + (right - left) / 2

        if predicate(s[mid]) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left, left < len(s)  // [F, F, F, F] where no element satisfies the predicate
}

predicate is a function that asserts whether a given element of E satisfies the predicate.

Again, if you don’t want to write this yourself, you can always use the built-in sort.Search.

import "sort"

func main() {
    s := []T{ /* omitted */ }
    target := T{ /* omitted */ }
    
    found := sort.Search(len(s), func(pos int) bool {
        return s[pos] >= target
    })
}

import "sort"

func main() {
    s := []T{ /* omitted */ }
    target := T{ /* omitted */ }
    
    found := sort.Search(len(s), func(pos int) bool {
        return s[pos] >= target
    })
}

The funny part about sort.Search is that it doesn’t take in the slice, or the element type itself. It only wants to know the range [) available for searching, and a function func(int) bool as the predicate which accesses the slice with an index.

Links:

• cmp.Ordered: https://cs.opensource.google/go/go/+/refs/tags/go1.27.2:src/cmp/cmp.go;drc=1a0b86375fad202048adb88cba4caec535a52a45;l=18
• slices.BinarySearch: https://cs.opensource.google/go/go/+/refs/tags/go1.27.2:src/slices/sort.go;l=126
• sort.Search: