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, and this pattern shows up constantly.

Start with the full concept guide: Binary Search Algorithm: A Coding Interview Guide.

What Do You Need Before Binary Search Works in Go?

  • A slice sorted in ascending order
  • Time complexity is O(log n), with O(1) extra space for the iterative version

How Do You Write the Iterative Version?

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 rarely a concern for ordinary index math, so (lo + hi) / 2 is usually safe in practice. Still, write lo + (hi-lo)/2 anyway, since that is the form interviewers expect and it stays safe even on inputs large enough to matter.

How Do You Write the 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)

The sort package implements binary search internally through sort.Search:

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 a lower bound: it takes a predicate instead of a value directly, and it returns len(arr) if nothing in the slice satisfies that predicate.

How Do You Write a Lower Bound Helper by Hand?

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
}

Reach for this pattern when a problem asks for an insertion point or the first index where arr[i] is greater than or equal to x, rather than an exact match.

What Should You Watch for in a Go Interview?

Check for an empty slice before you search it: if len(arr) == 0, return -1 immediately rather than letting the loop run on an empty range. Slices in Go are references, so passing one to a function never copies the underlying array, which is worth mentioning if an interviewer asks about memory. Stay consistent with your pointer names too: pick lo and hi, or left and right, and use the same pair throughout the solution instead of mixing conventions mid-function. In real projects you would back this with go test and table-driven cases, and it helps to say so even though you will not run tests live on a whiteboard.

How Do You Test the Implementation?

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)
    }
}

What's the Time and Space Complexity?

Both versions run in O(log n) time. The iterative version uses O(1) space, while the recursive version uses O(log n) space for the call stack, since each recursive call adds a frame that stays alive until the base case returns.