Introduction
According to "Programming Pearls" by Jon Bentley, only 10% of professional software engineers can write a correct binary search - one of the fundamental algorithms you first learn. Common mistakes include integer overflow, off by 1 errors, and infinite loops (time limit exceeded). Now is the time to finally master this method once and for all.
Context:
Consider the problem of finding a target number in a sorted array.
A linear scan takes O(n), however this is wasteful. Instead consider initializing a range of [left, right] = [0, len(arr)-1]. The middle number is simply (left+right)//2. If it is >= our target we can recurse on the left half (including this middle number, so right = mid, hence range is now [left, mid]). Otherwise, it is less than our target so we know the target cannot be in the left half of the array, so we can recurse solely on the right half (excluding this middle number, so left = mid+1, hence range is now [mid+1, right]). We recurse until left == right, meaning left is the index of target. This takes O(logn) time - a significant improvement.
Intuitively you want to imagine your range [left, right] shrinking by a factor of two each iteration, until left == right meaning your range has size exactly 1, and so this last value must be what you are looking for.
Although most commonly binary search is used to search over arrays, note that as long as our boolean "check" function (how we are deciding whether to recurse left or recurse right) is MONOTONIC on our range [left, right], binary search can be applied. (Monotonic boolean function means of the form of all Falses then all Trues or vice versa)
Sample Walkthrough
[1,2,3,4,5], target = 4
- Left = 0, right = 4. Mid = 2. Arr[mid] < target, so we recurse on the right half by setting left = mid+1.
- Left = 3, right = 4. Mid = 3. Arr[mid] >= target, so we recurse on the left half by setting right = mid.
- Left = 3, right = 3. Left == right so we stop the iteration. Index 3 is our answer, and indeed arr[3] = 4.
2 Templates for Binary Search
There are two main templates depending on whether you're searching for a minimum or maximum value.
Key: When solving binary search problems, characterize them in point form:
1. Min or max template
2. Initialize range: Left = ?, right = ?
3. Check function: check(mid) = ?
4. (perhaps some pre/post processing)
With this point form you should immediately know what the code looks like!
You will need to initialize left, right correctly to the exact range of values you want to search over. [left, right] = the SOLUTION space. For arrays, often left = 0, right = len(arr)-1 (the min/max indices).
Instead of mid = (left+right)//2, this handles overflow, as it is possible for left+right to be > INT_MAX.
This solves the INFINITE LOOP problem. When we set left = mid, it is possible for the while loop to never terminate. Consider [1,2] with max template and mid = (left+right)//2, left = 0, right = 1. If check(0) is true, we keep setting left = mid = 0, and our range [0,1] never decreases. Hence we need to take the ceiling to round up.
After the while loop, left == right so we can return either left or right.
Min case: …FFFTTT… If check(mid) is true and we want the minimum true, mid might be the answer but we should still check left. Hence right = mid. Otherwise left = mid + 1.
Max case: …TTTFFF… If check(mid) is true and we want the max true, mid might be the answer but we should still check right. Hence left = mid. Otherwise right = mid - 1.
We can also write these recursively. Correctness follows inductively.
O(log(right-left))O(1)1. Min Template - Searching for the minimum
Visualization:
FFF…FFFTTTT…TTTT [function range] (monotonically increasing)
0123… k … n [function domain]
We want the first T after all the F's (index k).
def binarySearchMin(...):
left, right = x, y
while left < right:
mid = left + (right-left)//2
if check(mid):
right = mid
else:
left = mid + 1
return left2. Max Template - Searching for the maximum
Visualization:
TTT…TTTFFFF…FFFF [function range] (monotonically decreasing)
0123… k … n [function domain]
We want the last T before all the F's (index k).
def binarySearchMax(...):
left, right = x, y
while left < right:
mid = ceil(left + (right-left)/2)
if check(mid):
left = mid
else:
right = mid - 1
return leftClassic Array Search
Direct application of binary search to find elements in sorted arrays.
01Binary SearchEasy
Given a sorted array and target, return the index of target or -1 if not found.
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left if nums[left] == target else -1O(log n)O(1)Min template with post-processing check. If multiple occurrences exist: Min template → leftmost, Max template → rightmost.
02Find First and Last Position of Element in Sorted ArrayMedium
Return first and last index of target in sorted array, or [-1, -1] if not found.
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
# Find leftmost (min template)
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
if nums[left] != target:
return [-1, -1]
first = left
# Find rightmost (max template)
left, right = 0, len(nums) - 1
while left < right:
mid = ceil(left + (right - left) / 2)
if nums[mid] <= target:
left = mid
else:
right = mid - 1
return [first, left]O(log n)O(1)Run both min and max templates. Min gives leftmost, max gives rightmost.
03Search Insert PositionEasy
Return index of target or where it would be inserted in sorted array.
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) # Note: right = len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return leftO(log n)O(1)No post-processing needed. Note right = len(nums) since target could be larger than all elements.
04First Bad VersionEasy
Find first bad version given isBadVersion(n) API. Versions [1..n].
def firstBadVersion(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return leftO(log n)O(1)Classic min template. Function is monotone: FFFTTT... Find first T.
Numeric Binary Search
Binary search over numbers rather than array indices. The search space is a numeric range.
01Sqrt(x)Easy
Return floor of square root of x.
def mySqrt(self, x: int) -> int:
left, right = 0, x
while left < right:
mid = ceil(left + (right - left) / 2)
if mid * mid <= x:
left = mid
else:
right = mid - 1
return leftO(log x)O(1)Max template since we want largest mid where mid² <= x. Min template with mid² >= x gives ceiling.
02Find Peak ElementMedium
Find index of element strictly greater than neighbors. nums[-1] = nums[n] = -∞.
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = ceil(left + (right - left) / 2)
if nums[mid - 1] <= nums[mid]:
left = mid
else:
right = mid - 1
return leftO(log n)O(1)Ternary search converted to binary search. Compare adjacent elements to determine which half contains a peak. Check nums[mid-1] <= nums[mid] creates monotone TTTFFF pattern.
03Peak Index in a Mountain ArrayMedium
Given a mountain array, return the index of its peak element.
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = ceil(left + (right - left) / 2)
if arr[mid - 1] <= arr[mid]:
left = mid
else:
right = mid - 1
return leftO(log n)O(1)Same peak-finding template as Find Peak Element, but the mountain-array guarantee means the peak is unique.
04Find in Mountain ArrayHard
Find target in a mountain array (increases then decreases). MountainArray interface has get(index) and length().
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
n = mountain_arr.length()
# Step 1: Find peak using Q162 approach
left, right = 0, n - 1
while left < right:
mid = ceil(left + (right - left) / 2)
if mountain_arr.get(mid - 1) <= mountain_arr.get(mid):
left = mid
else:
right = mid - 1
peak = left
# Step 2: Binary search left side (ascending)
left, right = 0, peak
while left < right:
mid = left + (right - left) // 2
if mountain_arr.get(mid) >= target:
right = mid
else:
left = mid + 1
if mountain_arr.get(left) == target:
return left
# Step 3: Binary search right side (descending)
left, right = peak, n - 1
while left < right:
mid = left + (right - left) // 2
if mountain_arr.get(mid) <= target:
right = mid
else:
left = mid + 1
return left if mountain_arr.get(left) == target else -1O(log n)O(1)Three binary searches: (1) find peak, (2) search ascending left half, (3) search descending right half. For descending, flip the comparison.
Binary Search on Answer
Instead of searching in an array, binary search over the answer space. Key insight: if we can verify whether a candidate answer works in O(n), we can find the optimal answer in O(n log k) where k is the answer range.
Pattern recognition:
1. Problem asks for minimum/maximum of something
2. The verification problem is easy (given candidate k, can check if it works)
3. The answer has monotonic feasibility (if k works, k+1 also works, or vice versa)
01Koko Eating BananasMedium
Find minimum eating speed k to finish all banana piles in h hours.
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def check(k):
return sum(ceil(p / k) for p in piles) <= h
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return leftO(n log(max(piles)))O(1)Min template. Search space is [1, max(piles)]. Check: can we finish in <= h hours at speed k?
02Maximum Candies Allocated to K ChildrenMedium
Find maximum candies per child when dividing piles among k children.
def maximumCandies(self, candies: List[int], k: int) -> int:
def check(size):
return sum(c // size for c in candies) >= k
left, right = 0, max(candies)
while left < right:
mid = ceil(left + (right - left) / 2)
if check(mid):
left = mid
else:
right = mid - 1
return leftO(n log(max(candies)))O(1)Max template. Same pattern as Koko but want maximum instead of minimum.
03Minimum Time to Complete TripsMedium
Find minimum time for buses to complete totalTrips. time[i] = trip duration for bus i.
def minimumTime(self, time: List[int], totalTrips: int) -> int:
def check(t):
return sum(t // bus for bus in time) >= totalTrips
left, right = 1, min(time) * totalTrips
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return leftO(n log(min(time) × totalTrips))O(1)Min template. Upper bound: slowest single bus completes all trips.
04Split Array Largest SumHard
Split array into k subarrays to minimize the maximum subarray sum.
def splitArray(self, nums: List[int], k: int) -> int:
def check(max_sum):
chunks, curr = 1, 0
for num in nums:
if num > max_sum:
return False
if curr + num > max_sum:
chunks += 1
curr = num
else:
curr += num
return chunks <= k
left, right = max(nums), sum(nums)
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return leftO(n log(sum(nums)))O(1)Min template. Search space: [max(nums), sum(nums)]. Check: can we split into <= k chunks where each <= mid?
05Divide ChocolateHard
Cut chocolate into k+1 pieces for you and k friends. You get the minimum piece. Maximize your piece.
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
def check(min_sweet):
pieces, curr = 0, 0
for s in sweetness:
curr += s
if curr >= min_sweet:
pieces += 1
curr = 0
return pieces >= k + 1
left, right = 1, sum(sweetness)
while left < right:
mid = ceil(left + (right - left) / 2)
if check(mid):
left = mid
else:
right = mid - 1
return leftO(n log(sum(sweetness)))O(1)Max template. Opposite of Q410 - this is MAX of the MIN. Greedy check: can we make k+1 pieces each with sum >= mid?
06Maximum Average Subarray IIHard
Find contiguous subarray of length >= k with maximum average.
def findMaxAverage(self, nums: List[int], k: int) -> float:
def check(avg):
# Transform: can we find subarray of len >= k with sum >= 0?
# After subtracting avg from each element
min_prefix = float('inf')
prefix = 0
lagging_prefix = 0
for i in range(len(nums)):
prefix += nums[i] - avg
if i >= k - 1:
if i == k - 1:
min_prefix = 0
if prefix >= min_prefix:
return True
lagging_prefix += nums[i - k + 1] - avg
min_prefix = min(min_prefix, lagging_prefix)
return False
left, right = min(nums), max(nums)
while right - left >= 1e-5:
mid = left + (right - left) / 2
if check(mid):
left = mid
else:
right = mid
return leftO(n log((max-min)/ε))O(1)Binary search on the average value. Key insight: subtract candidate avg from all elements, then find subarray of len >= k with sum >= 0. Uses prefix sum with delayed minimum tracking.