Binary Search and Selection

Updated

October 31, 2026

Binary Search and Selection

Binary search locates elements in a sorted collection by halving the search space on each step, finding targets in \(O(\log n)\) time. Selection algorithms (such as Quickselect) find the \(k\)-th smallest element (such as the median or 95th percentile latency) in \(O(n)\) average time without paying the full \(O(n \log n)\) cost to sort the entire dataset. The boring default in Go is slices.BinarySearch, but understanding partition boundaries is essential for range searches and percentile metrics.

Mental model

Binary Search Halving

On an array of 1,000,000 sorted elements, linear search takes up to 1,000,000 checks. Binary search takes at most 20 checks (\(\log_2 1000000 \approx 19.9\)).

Target: 38
[ 10, 14, 19, 26, 31, 38, 42, 55, 70 ]  Mid = idx 4 (31). 38 > 31 -> Search Right
                      [ 38, 42, 55, 70 ]  Mid = idx 6 (42). 38 < 42 -> Search Left
                      [ 38 ]              Mid = idx 5 (38). Match found!

Quickselect vs Full Sort

If a desk manager wants to find the median ticket resolution time in an array of 500,000 tickets:

Sorting then indexing: \(O(n \log n) \approx 9{,}500{,}000\) operations.
Quickselect: Discards half the partitions on each step (\(n + n/2 + n/4 + \dots \approx 2n\)) \(\to O(n) \approx 1{,}000{,}000\) operations.

Quickselect (Finding 3rd smallest element):
Partition around Pivot P:
[ Left: < P ]  [ P ]  [ Right: > P ]
       \
   Pivot lands at index 5. We need index 3 -> Recurse ONLY into Left partition!
   (Right partition is completely ignored!)

Worked examples

Case 1: Binary Search with Insertion Point Bounds

Save as binary_search_bounds.go. Implement binary search that finds the exact match or the insertion index where a new ticket should be inserted to preserve sorted order.

// binary_search_bounds.go
package main

import (
    "cmp"
    "fmt"
    "slices"
)

// LowerBound returns the first index where items[i] >= target.
func LowerBound[T cmp.Ordered](items []T, target T) int {
    low := 0
    high := len(items)

    for low < high {
        // Prevent integer overflow: low + (high-low)/2 instead of (low+high)/2
        mid := low + (high-low)/2
        if items[mid] < target {
            low = mid + 1
        } else {
            high = mid
        }
    }
    return low
}

func main() {
    // Sorted desk order arrival timestamps (in minutes from shift start)
    timestamps := []int{5, 12, 18, 24, 24, 24, 39, 55}
    fmt.Println("Sorted arrivals:", timestamps)

    // Custom LowerBound
    idx := LowerBound(timestamps, 24)
    fmt.Printf("First arrival >= 24 min: index %d (value: %d)\n", idx, timestamps[idx])

    // New arrival at minute 30
    insertIdx := LowerBound(timestamps, 30)
    fmt.Printf("Slot to insert arrival at min 30: index %d\n", insertIdx)

    // Go standard library slices.BinarySearch
    pos, found := slices.BinarySearch(timestamps, 39)
    fmt.Printf("slices.BinarySearch(39): found=%t at index %d\n", found, pos)

    posMissing, foundMissing := slices.BinarySearch(timestamps, 30)
    fmt.Printf("slices.BinarySearch(30): found=%t, insert position=%d\n", foundMissing, posMissing)
}

Run:

go run binary_search_bounds.go

Output:

Sorted arrivals: [5 12 18 24 24 24 39 55]
First arrival >= 24 min: index 3 (value: 24)
Slot to insert arrival at min 30: index 6
slices.BinarySearch(39): found=true at index 6
slices.BinarySearch(30): found=false, insert position=6

Case 2: Quickselect for Median and Percentile Calculation

Save as quickselect_desk.go. Find the median ticket resolution duration in \(O(n)\) average time.

// quickselect_desk.go
package main

import (
    "cmp"
    "fmt"
)

// Quickselect finds the k-th smallest element (0-indexed) in items.
// Mutates items in-place.
func Quickselect[T cmp.Ordered](items []T, k int) T {
    low := 0
    high := len(items) - 1

    for low <= high {
        pivotIdx := partition(items, low, high)
        if pivotIdx == k {
            return items[k]
        } else if pivotIdx < k {
            low = pivotIdx + 1
        } else {
            high = pivotIdx - 1
        }
    }
    return items[k]
}

func partition[T cmp.Ordered](items []T, low, high int) int {
    pivot := items[high]
    i := low
    for j := low; j < high; j++ {
        if items[j] < pivot {
            items[i], items[j] = items[j], items[i]
            i++
        }
    }
    items[i], items[high] = items[high], items[i]
    return i
}

func main() {
    // Ticket resolution durations in seconds
    durations := []int{320, 120, 450, 90, 600, 210, 180, 510, 290}
    fmt.Println("Raw durations:", durations)

    n := len(durations)
    medianIdx := n / 2 // Index 4 in 9-element slice

    medianVal := Quickselect(durations, medianIdx)
    fmt.Printf("Median resolution time: %d seconds (50th percentile)\n", medianVal)

    p90Idx := int(float64(n) * 0.9)
    p90Val := Quickselect(durations, p90Idx)
    fmt.Printf("90th percentile resolution time: %d seconds\n", p90Val)
}

Run:

go run quickselect_desk.go

Output:

Raw durations: [320 120 450 90 600 210 180 510 290]
Median resolution time: 290 seconds (50th percentile)
90th percentile resolution time: 600 seconds

The trap

The most famous bug in computer science history was in binary search: calculating mid = (low + high) / 2. In 32-bit systems or large datasets, low + high can overflow signed integer bounds into negative values, resulting in an index-out-of-bounds panic. The safe formula is always mid = low + (high-low)/2 or uint(low+high) >> 1.

Furthermore, binary search assumes the slice is already sorted. Calling binary search on an unsorted slice fails silently, returning wrong indices and false negatives.

The boring rule

Always use slices.BinarySearch or slices.BinarySearchFunc in production Go. It handles boundaries, returns the insertion position if missing, and is thoroughly tested.
Verify that your data is sorted before initiating binary search.
If you need the median, minimum, maximum, or arbitrary percentile of a large slice and do not need the rest of the slice sorted, use Quickselect instead of sorting the whole slice.
When calculating midpoints, always use low + (high - low)/2.

Try this

Use slices.BinarySearchFunc on a slice of DeskTicket structs to find tickets by customer email.
Implement a CountOccurrences(items []T, target T) int function that uses two binary searches (LowerBound and UpperBound) to count matches in \(O(\log n)\) time.