12.4 Binary Search | Algorithm Patterns | Infrastructure Development with Go

Binary search finds a value (or a boundary) in O(log n).

1 · Before you read — commit to an answer

versions := []string{"v1.2.0", "v1.3.0", "v1.6.0", "v2.0.0"}
fmt.Println(sort.SearchStrings(versions, "v1.5.0"))

Wrong is fine — the sort.Search section below explains the rule.

Classic Binary Search

// Find a config version in a sorted version list
func findVersion(versions []string, target string) int {
    lo, hi := 0, len(versions)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2 // avoid overflow vs (lo+hi)/2
        if versions[mid] == target {
            return mid
        } else if versions[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1 // not found
}

Go's sort.Search

import "sort"

// Find the first version >= "v1.5.0"
versions := []string{"v1.2.0", "v1.3.0", "v1.5.0", "v1.6.0", "v2.0.0"}
i := sort.SearchStrings(versions, "v1.5.0")
// i == 2

// Generic: find first index where f(i) is true
i = sort.Search(len(versions), func(i int) bool {
    return versions[i] >= "v1.5.0"
})

Binary Search on the Answer

2 · Worked example — read every step

"What's the minimum number of servers to handle N requests, given each server handles at most M?"

// Binary search on answer: minimum servers needed
func minServers(requests int, perServer int) int {
    lo, hi := 1, requests
    for lo < hi {
        mid := lo + (hi-lo)/2
        if mid*perServer >= requests {
            hi = mid // might be enough
        } else {
            lo = mid + 1 // not enough
        }
    }
    return lo
}

The pattern: When the answer is monotonic (if X servers work, X+1 also works), binary search the answer space.

3 · Fill the gaps

Exact-match binary search over sorted latencies — mind the loop condition and how each boundary moves past mid.

lo, hi := 0, len(latencies)-1
for  {
    mid := lo + 
    switch {
    case latencies[mid] == target:
        return mid
    case latencies[mid] < target:
        
    default:
        
    }
}
return -1

Compare with the boundary search above: the loop condition and the hi move are both different, and mixing the two styles is the classic infinite-loop bug.

4 · From scratch — this feeds your review queue