Why Binary Search Is Tested So Frequently
Binary search appears in roughly 10-15% of FAANG coding interviews, both as a standalone problem and as a subroutine inside harder problems. The core algorithm is simple — O(log n) search in a sorted array — but interview problems disguise it as: finding a boundary condition, searching in a rotated array, or applying binary search to an answer space rather than an array. Mastering the three main templates removes 95% of the difficulty.
Template 1: Standard Binary Search
def binary_search(nums: list, target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right: # <= because single element is valid
mid = left + (right - left) // 2 # avoids integer overflow
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # not found
# Time: O(log n), Space: O(1)
The overflow-safe mid calculation: left + (right – left) // 2 is equivalent to (left + right) // 2 but prevents integer overflow when left and right are large. In Python this is academic (arbitrary precision ints), but critical in Java and C++ where int overflow is a real bug.
Template 2: Find Left / Right Boundary
Many problems ask for the first or last occurrence of a value, or the leftmost position where a condition becomes true. Use this template instead of Template 1.
# Find leftmost (first) occurrence of target
def find_left(nums: list, target: int) -> int:
left, right = 0, len(nums) # right is len, not len-1
while left < right: # strictly less than
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid # do not exclude mid yet
return left if left int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target: # note: <= instead of = 0 and nums[pos] == target else -1
# Count occurrences of target in sorted array
def count(nums, target):
return find_right(nums, target) - find_left(nums, target) + 1
Template 3: Binary Search on Answer
Some problems have no explicit sorted array but have a monotonic property: there is a threshold value X such that all values below X fail the condition and all values above pass (or vice versa). Binary search finds X in O(log(range)) time.
# Koko eating bananas: find minimum eating speed to finish all piles in H hours
def min_eating_speed(piles: list, H: int) -> int:
def can_finish(speed: int) -> bool:
hours = sum(-(-p // speed) for p in piles) # ceiling division
return hours <= H
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
right = mid # try slower speed
else:
left = mid + 1 # need faster speed
return left
# Minimum days to make M bouquets — same pattern
# Minimum capacity to ship packages in D days — same pattern
# Pattern: binary search on the answer value, use feasibility check function
Classic Problem: Search in Rotated Sorted Array
# Array [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7]
def search_rotated(nums: list, target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Determine which half is sorted
if nums[left] <= nums[mid]: # left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1 # target in sorted left half
else:
left = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1 # target in sorted right half
else:
right = mid - 1
return -1
Search in 2D Matrix
# Matrix where each row is sorted and first element of each row > last of prev row
# Treat as flattened 1D sorted array
def search_matrix(matrix: list, target: int) -> bool:
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
val = matrix[mid // n][mid % n] # convert 1D index to 2D
if val == target: return True
elif val bool:
row, col = 0, len(matrix[0]) - 1
while row = 0:
if matrix[row][col] == target: return True
elif matrix[row][col] > target: col -= 1 # too big, go left
else: row += 1 # too small, go down
return False
Common Binary Search Interview Problems
- Template 1: Binary Search, Guess Number Higher or Lower, First Bad Version
- Template 2: Find First and Last Position, Find Minimum in Rotated Array, Peak Index in Mountain Array
- Template 3: Koko Eating Bananas, Capacity to Ship Packages, Minimum Days to Make Bouquets, Median of Two Sorted Arrays
- Rotated array: Search in Rotated Sorted Array (I and II with duplicates)
- 2D: Search a 2D Matrix (I and II), Kth Smallest in Sorted Matrix
Interview Approach
- Identify monotonicity: if the problem has a sorted array OR a condition that flips from false to true at some threshold, binary search applies
- Choose the right template before writing code — boundary template bugs are the most common interview mistake
- Loop invariant: know what left and right mean at every iteration
- Always check: what does the loop return when target is not found?
- Off-by-one: use left less than right (Template 2/3) or left less than or equal to right (Template 1) consistently
Frequently Asked Questions
What are the three binary search templates and when do you use each?
Template 1 (standard): find a specific target value in a sorted array. Loop condition: left <= right. Returns the index of target or -1. Use for: basic search, fixed target value. Template 2 (boundary): find the leftmost or rightmost position where a condition is true. Loop condition: left < right (strictly less than). Right initializes to len(nums), not len(nums)-1. The loop exits with left == right pointing to the answer. Use for: first/last occurrence, minimum in rotated array, peak finding. Template 3 (answer space): binary search on the answer value rather than an array index. Define a feasibility function that returns true or false. Binary search finds the minimum (or maximum) value for which feasibility is true. Use for: Koko eating bananas, capacity to ship packages, minimum days to make bouquets. Recognizing which template applies is the key skill.
How do you search in a rotated sorted array?
A rotated sorted array like [4,5,6,7,0,1,2] still has the property that at least one half (from mid to left or mid to right) is always sorted. The algorithm: check if the left half (nums[left] to nums[mid]) is sorted. If nums[left] <= nums[mid], the left half is sorted. Then check if the target falls within the sorted left half — if yes, search left; otherwise search right. If the left half is not sorted, the right half must be sorted. Check if target falls within the sorted right half — if yes, search right; otherwise search left. This produces an O(log n) solution without needing to find the rotation point first. For the follow-up with duplicates (nums[left] == nums[mid] is ambiguous), increment left by one to shrink the ambiguous case, making worst case O(n).
What is binary search on the answer and how do you recognize it?
Binary search on the answer applies when: (1) the answer is a value within a known range (not an index in an array), (2) there is a monotonic feasibility function — values below the threshold are infeasible and above are feasible (or vice versa), and (3) a brute force search over all possible answers would be too slow. The pattern: set left = minimum possible answer, right = maximum possible answer, write a can_achieve(mid) function that tests whether answer mid is feasible, then binary search to find the minimum feasible value. Examples: find minimum eating speed so all piles are eaten in H hours (feasibility: total hours at this speed <= H); find minimum ship capacity to deliver all packages in D days (feasibility: packages fit in D days at this capacity). The feasibility function often runs in O(n), making the total complexity O(n log(range)).
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “What are the three binary search templates and when do you use each?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Template 1 (standard): find a specific target value in a sorted array. Loop condition: left <= right. Returns the index of target or -1. Use for: basic search, fixed target value. Template 2 (boundary): find the leftmost or rightmost position where a condition is true. Loop condition: left < right (strictly less than). Right initializes to len(nums), not len(nums)-1. The loop exits with left == right pointing to the answer. Use for: first/last occurrence, minimum in rotated array, peak finding. Template 3 (answer space): binary search on the answer value rather than an array index. Define a feasibility function that returns true or false. Binary search finds the minimum (or maximum) value for which feasibility is true. Use for: Koko eating bananas, capacity to ship packages, minimum days to make bouquets. Recognizing which template applies is the key skill." } }, { "@type": "Question", "name": "How do you search in a rotated sorted array?", "acceptedAnswer": { "@type": "Answer", "text": "A rotated sorted array like [4,5,6,7,0,1,2] still has the property that at least one half (from mid to left or mid to right) is always sorted. The algorithm: check if the left half (nums[left] to nums[mid]) is sorted. If nums[left] <= nums[mid], the left half is sorted. Then check if the target falls within the sorted left half — if yes, search left; otherwise search right. If the left half is not sorted, the right half must be sorted. Check if target falls within the sorted right half — if yes, search right; otherwise search left. This produces an O(log n) solution without needing to find the rotation point first. For the follow-up with duplicates (nums[left] == nums[mid] is ambiguous), increment left by one to shrink the ambiguous case, making worst case O(n)." } }, { "@type": "Question", "name": "What is binary search on the answer and how do you recognize it?", "acceptedAnswer": { "@type": "Answer", "text": "Binary search on the answer applies when: (1) the answer is a value within a known range (not an index in an array), (2) there is a monotonic feasibility function — values below the threshold are infeasible and above are feasible (or vice versa), and (3) a brute force search over all possible answers would be too slow. The pattern: set left = minimum possible answer, right = maximum possible answer, write a can_achieve(mid) function that tests whether answer mid is feasible, then binary search to find the minimum feasible value. Examples: find minimum eating speed so all piles are eaten in H hours (feasibility: total hours at this speed <= H); find minimum ship capacity to deliver all packages in D days (feasibility: packages fit in D days at this capacity). The feasibility function often runs in O(n), making the total complexity O(n log(range))." } } ] }