Classic Binary Search
Maintain a half-open range and discard half of it each step based on a comparison with the midpoint.
Binary SearchO(log n)New20 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
sorted input
find target or insertion point
first or last occurrence
The template
Get this into muscle memory, then adapt the condition per problem.
let lo = 0, hi = n - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (a[mid] === target) return mid;
a[mid] < target ? (lo = mid + 1) : (hi = mid - 1);
} Watch Binary SearchIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Sorted input plus a log-time requirement is almost always binary search.
- 2Write down what lo and hi mean before the loop and keep it true.
- 3For boundaries, do not return early; keep narrowing and record candidates.
Drill it
Every problem in the bank that uses this pattern.
0 / 20 solved