Binary Search: when to spot it, explain it, and practice it
Binary search is really about exploiting monotonicity. The strongest candidates stop thinking about arrays only and start thinking about predicates that flip from false to true.
Pattern coverage
40+
Best first move
Define the predicate before choosing loop bounds.
Common failure point
Using the wrong interval convention and causing infinite loops.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Write the monotonic predicate in plain English first.
Choose a search interval that definitely contains the answer.
Use mid to test feasibility, not to guess blindly.
Move one boundary and preserve the invariant every time.
Return the boundary that represents the first feasible or last infeasible point.
Common variants
Exact match
The classic sorted-array search for a target.
Boundary search
Find the first or last position satisfying a condition.
Answer-space search
Binary search on capacity, speed, or some feasible answer rather than an array index.
Template preview
# Find first position where check(mid) is true
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
Classic problems with useful framing
#33
Search in Rotated Sorted Array
Great for reasoning about partially ordered halves.
Search for a target in a rotated sorted array.
#34
Find First and Last Position
Best starter for left boundary and right boundary logic.
Return the first and last index of a target in a sorted array.
#69
Sqrt(x)
A clean example of binary searching an answer value.
Compute the integer square root of x.
#4
Median of Two Sorted Arrays
A harder binary-search question that tests partition reasoning.
Find the median of two sorted arrays in logarithmic time.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#69 Sqrt(x)
Compute the integer square root of x.
You are not searching array positions; you are searching the feasible numeric answer boundary.
Foundation
#33 Search in Rotated Sorted Array
Search for a target in a rotated sorted array.
You are not comparing target with random values; you are using sorted-half structure to eliminate half the array safely.
Variant depth
#34 Find First and Last Position
Return the first and last index of a target in a sorted array.
The left boundary and right boundary are two different predicates and deserve two separate searches.
Variant depth
#4 Median of Two Sorted Arrays
Find the median of two sorted arrays in logarithmic time.
Binary search on the partition index of the shorter array because the partition in the longer array is then determined automatically.
High-frequency mistakes
Using the wrong interval convention and causing infinite loops.
Returning mid instead of the boundary.
Failing to prove monotonicity before starting.
Overflow or off-by-one issues when computing mid and boundaries.
Recommended practice path
Start with boundary problems such as first/last position.
Then solve rotated-array and peak-style questions.
After that, move to answer-space problems like shipping capacity and minimum speed.
Review exact-match binary search last so boundary intuition stays dominant.