Binary search repeatedly halves the search space by comparing the target with the middle element. It works on any sorted or monotonic data.
Use when: the input is sorted, or you can define a monotonic predicate (true/false boundary) over a range.
Classic binary search: find the index of target in a
sorted slice. Returns -1 if not found.
Avoid integer overflow with (lo+hi)/2
If the target is larger, discard the left half. If smaller, discard the right half.
A more general form: “search on answer”. Instead of searching an array, we binary search a range of possible answers and test each with a predicate.
Example: find the minimum speed to finish eating all
piles of bananas in h hours.
canFinish is our monotonic predicate: once true at speed k, it stays true for all k’ > k.
Trace: nums = [1, 3, 5, 7, 9, 11], target = 7
lo=0, hi=5, mid=2: nums[2]=5 < 7, lo=3 lo=3, hi=5, mid=4: nums[4]=9 > 7, hi=3 lo=3, hi=3, mid=3: nums[3]=7 == 7, found!
func binarySearch(nums []int, target int) int {
lo, hi := 0, len(nums)-1
for lo <= hi { mid := lo + (hi-lo)/2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1
}
func minEatingSpeed(piles []int, h int) int {
lo, hi := 1, 0
for _, p := range piles {
if p > hi {
hi = p
}
}
canFinish := func(speed int) bool {
hours := 0
for _, p := range piles {
hours += (p + speed - 1) / speed
}
return hours <= h
}
for lo < hi {
mid := lo + (hi-lo)/2
if canFinish(mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func main() {
fmt.Println(binarySearch([]int{1, 3, 5, 7, 9, 11}, 7))
fmt.Println(binarySearch([]int{1, 3, 5, 7, 9, 11}, 4))
fmt.Println(minEatingSpeed([]int{3, 6, 7, 11}, 8))
fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 5))
}