LiveCodingInterview.com
← Articles

How to Implement Binary Search in Go

Go's simplicity makes binary search easy to read on a whiteboard — slices, integer indices, and no hidden overflow surprises with size_t. Many backend interviews use Go; this pattern shows up constantly.

For algorithm theory and interview variants, read Binary Search Algorithm: A Coding Interview Guide first.

Prerequisites

  • Slice sorted in ascending order
  • **O(log n)** time, **O(1)** extra space (iterative)
func binarySearch(arr []int, x int) int {
    lo, hi := 0, len(arr)-1

    for lo <= hi {
        mid := lo + (hi-lo)/2

        if arr[mid] == x {
            return mid
        }
        if arr[mid] > x {
            hi = mid - 1
        } else {
            lo = mid + 1
        }
    }

    return -1
}

Go integers are signed and arbitrary precision is not an issue for indices — `(lo + hi) / 2` is usually safe, but `lo + (hi-lo)/2` is still the interview-standard form.

Recursive version

func binarySearchRec(arr []int, x, lo, hi int) int {
    if lo > hi {
        return -1
    }
    mid := lo + (hi-lo)/2

    if arr[mid] == x {
        return mid
    }
    if arr[mid] > x {
        return binarySearchRec(arr, x, lo, mid-1)
    }
    return binarySearchRec(arr, x, mid+1, hi)
}

// Call: binarySearchRec(arr, x, 0, len(arr)-1)

sort.Search (idiomatic Go)

The standard library uses binary search internally:

import "sort"

arr := []int{1, 3, 5, 7, 9}
x := 5

// Smallest index i where arr[i] >= x
idx := sort.Search(len(arr), func(i int) bool {
    return arr[i] >= x
})

found := idx < len(arr) && arr[idx] == x
_ = found

`sort.Search` is the Go equivalent of lower bound. It returns `len(arr)` if no element satisfies the predicate.

Lower bound helper

func lowerBound(arr []int, x int) int {
    lo, hi := 0, len(arr)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if arr[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

Use when the problem asks for insertion point or first index where `arr[i] >= x`.

Go-specific tips

  • Check empty slice: `if len(arr) == 0 { return -1 }`
  • Slices are references — no copying when passing to functions
  • Naming: `lo`/`hi` or `left`/`right` — stay consistent
  • Run tests with `go test` and table-driven cases in real projects

Example test

func TestBinarySearch(t *testing.T) {
    arr := []int{1, 3, 5, 7, 9}
    if got := binarySearch(arr, 5); got != 2 {
        t.Fatalf("got %d, want 2", got)
    }
    if got := binarySearch(arr, 4); got != -1 {
        t.Fatalf("got %d, want -1", got)
    }
}

Complexity

  • **Time:** O(log n)
  • **Space:** O(1) iterative, O(log n) recursive