Core patterns · Lesson 19 of 62 · about 50 min
Binary search
Halve the search space every step for O(log n), write the loop without off-by-one bugs, and search on the answer when there is no array at all.
On this page · 9 sections
The loop that never has off-by-one bugs#
Most binary search bugs come from mixing up inclusive and exclusive bounds. Use one convention everywhere: the half-open range [lo, hi), meaning lo is a candidate and hi is not.
lowerBound: the first index whose value is >= target (or len(nums) if none).
lo, hi := 0, len(nums) // candidates: [lo, hi)
for lo < hi { // stop when the range is empty
mid := lo + (hi-lo)/2
if nums[mid] < target {
lo = mid + 1 // mid is too small: exclude it
} else {
hi = mid // mid might be the answer: keep it as the new exclusive end
}
}
return lo // lo == hi: the first index that is >= targetTrace nums = [1, 3, 5, 7, 9, 11], target = 7:
| lo | hi | mid | nums[mid] | < 7? | new range |
|---|---|---|---|---|---|
| 0 | 6 | 3 | 7 | no | hi = 3 → [0, 3) |
| 0 | 3 | 1 | 3 | yes | lo = 2 → [2, 3) |
| 2 | 3 | 2 | 5 | yes | lo = 3 → [3, 3) empty |
Return 3: nums[3] == 7. For a target that is missing, like 6, the same loop returns 3 too: the position where 6 would be inserted.
Run the trace
The same loop, printing every step. It searches for a target that exists and one that does not:
package main
import "fmt"
func lowerBound(nums []int, target int) int {
lo, hi := 0, len(nums)
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] < target {
fmt.Printf(" [%d,%d) mid=%d nums[mid]=%-2d < %d: lo = %d\n", lo, hi, mid, nums[mid], target, mid+1)
lo = mid + 1
} else {
fmt.Printf(" [%d,%d) mid=%d nums[mid]=%-2d >= %d: hi = %d\n", lo, hi, mid, nums[mid], target, mid)
hi = mid
}
}
return lo
}
func main() {
nums := []int{1, 3, 5, 7, 9, 11}
for _, t := range []int{7, 6, 12} {
fmt.Println("target", t)
fmt.Println(" result:", lowerBound(nums, t))
}
}target 7
[0,6) mid=3 nums[mid]=7 >= 7: hi = 3
[0,3) mid=1 nums[mid]=3 < 7: lo = 2
[2,3) mid=2 nums[mid]=5 < 7: lo = 3
result: 3
target 6
[0,6) mid=3 nums[mid]=7 >= 6: hi = 3
[0,3) mid=1 nums[mid]=3 < 6: lo = 2
[2,3) mid=2 nums[mid]=5 < 6: lo = 3
result: 3
target 12
[0,6) mid=3 nums[mid]=7 < 12: lo = 4
[4,6) mid=5 nums[mid]=11 < 12: lo = 6
result: 612 is larger than everything, so the answer is len(nums): "insert at the end".
Everything else is a variation:
| Question | Answer |
|---|---|
does target exist? | i := lowerBound(nums, t); i < len(nums) && nums[i] == t |
first index > target (upper bound) | change < to <= |
how many times does target occur? | upperBound - lowerBound |
| where to insert to keep sorted | lowerBound |
The standard library has both: slices.BinarySearch(s, x) returns (index, found), and sort.Search(n, f) returns the first i in [0, n) where f(i) is true.
Step through it
Try a target that is missing, smaller than everything, or larger than everything.
The standard library versions
package main
import (
"fmt"
"slices"
"sort"
)
func main() {
nums := []int{1, 3, 5, 5, 5, 9}
i, found := slices.BinarySearch(nums, 5) // first index of 5
fmt.Println(i, found)
i, found = slices.BinarySearch(nums, 4) // where 4 would go
fmt.Println(i, found)
// sort.Search finds the first index where the condition becomes true.
first := sort.Search(len(nums), func(i int) bool { return nums[i] >= 5 })
after := sort.Search(len(nums), func(i int) bool { return nums[i] > 5 })
fmt.Println("5 occurs", after-first, "times, at", first, "to", after-1)
// Insert while keeping the slice sorted.
i, _ = slices.BinarySearch(nums, 4)
nums = slices.Insert(nums, i, 4)
fmt.Println(nums)
}2 true
2 false
5 occurs 3 times, at 2 to 4
[1 3 4 5 5 5 9]Search on the answer#
Many problems have no sorted array, but they ask for the smallest value that works. If "does value x work?" is monotonic (false, false, …, false, true, true, …), binary search finds the first true.
"Koko must eat all banana piles within h hours, eating up to k bananas per hour from one pile. What is the minimum k?" At speed k, a pile p takes ceil(p / k) hours. Faster speeds never take longer, so the check is monotonic.
Trace piles = [3, 6, 7, 11], h = 8, searching speeds 1 to 11:
| speed k | hours = sum of ceil(p/k) | ≤ 8? |
|---|---|---|
| 6 (first mid) | 1 + 1 + 2 + 2 = 6 | yes: try slower |
| 3 | 1 + 2 + 3 + 4 = 10 | no: go faster |
| 4 | 1 + 2 + 2 + 3 = 8 | yes |
| 5 | (not needed: 4 works and 3 does not) |
The answer is 4, found in a handful of checks rather than trying every speed.
Run the trace
The search runs over speeds in [1, max+1). Each line shows the speed being tested and how many hours it needs:
package main
import "fmt"
func hoursAt(piles []int, k int) int {
h := 0
for _, p := range piles {
h += (p + k - 1) / k // ceil(p / k)
}
return h
}
func main() {
piles, h := []int{3, 6, 7, 11}, 8
lo, hi := 1, 12 // speeds 1..11
for lo < hi {
mid := lo + (hi-lo)/2
need := hoursAt(piles, mid)
if need <= h {
fmt.Printf("speed %2d: %2d hours, fits: try slower -> [%d,%d)\n", mid, need, lo, mid)
hi = mid
} else {
fmt.Printf("speed %2d: %2d hours, too slow: faster -> [%d,%d)\n", mid, need, mid+1, hi)
lo = mid + 1
}
}
fmt.Println("minimum speed:", lo)
}speed 6: 6 hours, fits: try slower -> [1,6)
speed 3: 10 hours, too slow: faster -> [4,6)
speed 5: 8 hours, fits: try slower -> [4,5)
speed 4: 8 hours, fits: try slower -> [4,4)
minimum speed: 4The real loop also tests speed 5, because at that moment it does not yet know that 4 works. It still needs only 4 checks instead of 11.
One template for every "search on the answer" problem
Every one of these problems has the same skeleton: a range of candidate answers, and a yes/no check that flips from false to true exactly once. Write the search once, generically, and each problem shrinks to its check function:
| Problem | Candidate answer | Check: "does x work?" |
|---|---|---|
| Koko eating bananas | eating speed | total hours at speed x ≤ h |
| ship packages within D days | ship capacity | greedily loading in order needs ≤ D days |
| split array largest sum | largest allowed part sum | greedy splitting needs ≤ k parts |
| minimum days to make m bouquets | a day number | by day x, enough adjacent flowers bloomed |
| aggressive cows / magnetic force | minimum distance | greedily placing items at gaps ≥ x fits all (search the largest true) |
package main
import (
"fmt"
"slices"
)
// firstTrue returns the smallest x in [lo, hi] with ok(x) true (ok must be monotonic), or hi+1.
func firstTrue(lo, hi int, ok func(int) bool) int {
hi++ // half-open [lo, hi)
for lo < hi {
mid := lo + (hi-lo)/2
if ok(mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
// daysNeeded loads packages in order onto ships of capacity cap.
func daysNeeded(weights []int, cap int) int {
days, load := 1, 0
for _, w := range weights {
if load+w > cap {
days++
load = 0
}
load += w
}
return days
}
func shipWithinDays(weights []int, d int) int {
sum := 0
for _, w := range weights {
sum += w
}
// The capacity must fit the heaviest package; it never needs more than everything at once.
return firstTrue(slices.Max(weights), sum, func(c int) bool { return daysNeeded(weights, c) <= d })
}
func splitArray(nums []int, k int) int {
sum := 0
for _, n := range nums {
sum += n
}
return firstTrue(slices.Max(nums), sum, func(limit int) bool {
return daysNeeded(nums, limit) <= k // same greedy: parts instead of days
})
}
func minDaysBouquets(bloom []int, m, k int) int {
if m*k > len(bloom) {
return -1
}
return firstTrue(slices.Min(bloom), slices.Max(bloom), func(day int) bool {
bouquets, run := 0, 0
for _, b := range bloom {
if b <= day {
run++
if run == k {
bouquets++
run = 0
}
} else {
run = 0
}
}
return bouquets >= m
})
}
// maxMinDistance places c items in sorted positions maximizing the smallest gap: the LAST x that works.
func maxMinDistance(pos []int, c int) int {
slices.Sort(pos)
fits := func(gap int) bool {
placed, last := 1, pos[0]
for _, p := range pos[1:] {
if p-last >= gap {
placed++
last = p
}
}
return placed >= c
}
// "fits" goes true, true, ..., false: the answer is just before the first false.
return firstTrue(1, pos[len(pos)-1]-pos[0], func(g int) bool { returnfits(g) }) - 1
}
func main() {
fmt.Println("ship capacity:", shipWithinDays([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5))
fmt.Println("split array:", splitArray([]int{7, 2, 5, 10, 8}, 2))
fmt.Println("bouquet day:", minDaysBouquets([]int{1, 10, 3, 10, 2}, 3, 1))
fmt.Println("max min distance:", maxMinDistance([]int{1, 2, 3, 4, 7}, 3))
}ship capacity: 15
split array: 18
bouquet day: 3
max min distance: 3Two details make these correct. The search range must contain the answer: the lower bound comes from "at least the biggest single item" and the upper bound from "everything at once always works". And "largest x that works" problems flip the check: search for the first x that fails and subtract one.
Rotated sorted arrays#
[4, 5, 6, 7, 0, 1, 2] was sorted, then rotated. At any mid, at least one half is sorted. Check whether the target falls inside the sorted half's range; if so, search there, otherwise search the other half. Still O(log n).
Run the trace
At each step the program says which half is sorted and whether the target can be inside it:
package main
import "fmt"
func main() {
nums, target := []int{4, 5, 6, 7, 0, 1, 2}, 0
lo, hi := 0, len(nums)-1 // inclusive bounds here, since we compare nums[lo] and nums[hi]
for lo <= hi {
mid := lo + (hi-lo)/2
fmt.Printf("lo=%d hi=%d mid=%d nums[mid]=%d ", lo, hi, mid, nums[mid])
if nums[mid] == target {
fmt.Println("found at", mid)
return
}
if nums[lo] <= nums[mid] { // left half is sorted
if nums[lo] <= target target < nums[mid] {
fmt.Printf("left %v sorted, target inside\n", nums[lo:mid+1])
hi = mid - 1
} else {
fmt.Printf("left %v sorted, target not inside\n", nums[lo:mid+1])
lo = mid + 1
}
} else { // right half is sorted
if nums[mid] < target target <= nums[hi] {
fmt.Printf("right %v sorted, target inside\n", nums[mid:hi+1])
lo = mid + 1
} else {
fmt.Printf("right %v sorted, target not inside\n", nums[mid:hi+1])
hi = mid - 1
}
}
}
fmt.Println("not found")
}lo=0 hi=6 mid=3 nums[mid]=7 left [4 5 6 7] sorted, target not inside
lo=4 hi=6 mid=5 nums[mid]=1 left [0 1] sorted, target inside
lo=4 hi=4 mid=4 nums[mid]=0 found at 4The full program#
package main
import (
"fmt"
"slices"
"sort"
)
func lowerBound(nums []int, target int) int {
lo, hi := 0, len(nums)
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
func search(nums []int, target int) int {
i := lowerBound(nums, target)
if i < len(nums) nums[i] == target {
return i
}
return -1
}
func minEatingSpeed(piles []int, h int) int {
// sort.Search tries i in [0, max); speed is i+1
return 1 + sort.Search(slices.Max(piles), func(i int) bool {
k := i + 1
hours := 0
for _, p := range piles {
hours += (p + k - 1) / k // ceil(p / k) with integers
}
return hours <= h
})
}
func searchRotated(nums []int, target int) int {
lo, hi := 0, len(nums)-1 // inclusive bounds here: both ends are candidates
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] == target {
return mid
}
if nums[lo] <= nums[mid] { // left half is sorted
if nums[lo] <= target target < nums[mid] {
hi = mid - 1
} else {
lo = mid + 1
}
} else { // right half is sorted
if nums[mid] < target target <= nums[hi] {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
return -1
}
func main() {
nums := []int{1, 3, 5, 7, 9, 11}
fmt.Println(lowerBound(nums, 7), lowerBound(nums, 6), lowerBound(nums, 99))
fmt.Println(search(nums, 9), search(nums, 4))
i, found := slices.BinarySearch(nums, 5)
fmt.Println(i, found)
fmt.Println(minEatingSpeed([]int{3, 6, 7, 11}, 8), minEatingSpeed([]int{30, 11, 23, 4, 20}, 5))
fmt.Println(searchRotated([]int{4, 5, 6, 7, 0, 1, 2}, 0), searchRotated([]int{4, 5, 6, 7, 0, 1, 2}, 3))
}3 3 6
4 -1
2 true
4 30
4 -1Complexity#
| Operation | Time | Space |
|---|---|---|
| search in sorted slice | O(log n) | O(1) |
| search on the answer over range R, check costs C | O(C · log R) | O(1) |
| rotated array search | O(log n) | O(1) |
For Koko: the check costs O(n) and the range is up to max(piles), so O(n log max).
Recognizing the pattern#
- The input is sorted, or a function of the index is monotonic.
- The question asks for the minimum value that satisfies something, or the maximum that does not: "minimum capacity", "smallest speed", "largest minimum distance".
- Constraints allow O(n log n) or O(log n), but a linear scan over the answer range would be too slow.
Summary#
- Binary search halves the candidates each step: O(log n).
- Use half-open
[lo, hi),for lo < hi,lo = mid + 1,hi = mid; the result is the lower bound. slices.BinarySearchandsort.Searchcover most needs in the standard library.- Search on the answer whenever a yes/no check is monotonic in the value.
- Rotated arrays: one half is always sorted; decide which half can contain the target.
Check your understanding
Answer before scrolling back up. If you miss one, reread the matching section, then try again.
Q1.How many steps does binary search need for 1,000,000 sorted elements, at most?
Q2.With the half-open range
[lo, hi)andfor lo < hi, whennums[mid] >= targetyou set:Q3.Why write
mid := lo + (hi-lo)/2instead of(lo+hi)/2?Q4.Search on the answer requires the yes/no check to be:
Practice in Go
Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.
- Binary Search ↗easy
Show hint
lowerBound, then check whether the index is in range and holds the target.
Show hint
This is exactly lowerBound.
Show hint
isBadVersion is monotonic: find the first true.
- Koko Eating Bananas ↗medium
Show hint
Search speeds 1..max(piles); hours needed is the sum of ceil(p/k).
Show hint
At each mid, one half is sorted. Check if the target lies in that half's range.
Show hint
Binary search the cut position in the shorter array so both left halves together hold half the elements.
Finished this lesson?
Mark it done to track your progress. It is saved in this browser only.