Master Binary Search: From Basics to Advanced Patterns
A comprehensive guide to binary search algorithms, covering standard search, rotated arrays, and finding boundaries.
Binary search is one of the most powerful algorithmic techniques. When applied correctly, it can reduce O(n) problems to O(log n).
The Basic Pattern
Binary search works on sorted arrays by repeatedly dividing the search space in half.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Finding Boundaries
Often, you need to find the first or last occurrence.
def find_first(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # Continue searching left
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return resultSearch in Rotated Array
A common variation is searching in a rotated sorted array.
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Key Patterns
- Standard search finds an exact match.
- Boundary search finds the first or last valid position.
- Rotated arrays let you search partially sorted data.
- Search space. Apply to non-array problems
Master these patterns, and binary search becomes a powerful tool in your arsenal!
How to practice this skill
Treat this topic as a loop rather than a fact to memorize. First, name the pattern in plain English. Then write the smallest version that proves you understand the invariant. Only after that should you chase speed. That order matters because most interview mistakes are not typing mistakes; they are recognition mistakes. You reach for the right data structure too late, or you optimize before you have named what must stay true.
For binary search practice, the useful repetition is spaced. Solve one problem slowly, rewrite the solution from memory the next day, then do a timed variant after the idea feels boring. The second pass is where the pattern moves from recognition to recall. The timed pass is where it becomes usable under pressure.
Implementation checklist
- Restate the input and output before coding.
- Write down the invariant or decision rule in one sentence.
- Test the smallest case, the largest obvious case, and the case that breaks the naive approach.
- Compare the final complexity to the constraint that actually matters.
The checklist is intentionally short. A long checklist becomes another thing to memorize. A short one becomes a rhythm you can run in a blank editor, in a live interview, or in an AlgoArena battle.
Edge cases worth drilling
Most missed solutions come from one of three places: empty input, duplicated values, or a boundary that looks harmless until the loop reaches it. When you review a solution, do not only ask whether it passed. Ask which boundary made the implementation honest.
If a solution uses indexes, trace the first and last iteration. If it uses a map or set, trace the duplicate case. If it uses recursion, name the base case and the state that gets smaller. These small reviews are faster than solving a new problem and often teach more.
How it transfers to real work
The interview version is compact, but the habit transfers. Production bugs often come from the same failure mode: unclear invariants under changing data. A developer who can name the invariant, test the boundary, and explain the tradeoff is easier to trust than someone who only remembers a trick.
That is why AlgoArena treats practice as observable work. The point is not to collect solved badges. The point is to build a repeatable way of thinking that survives a clock, an unfamiliar prompt, and another person reading over your shoulder.
Review drill
Before you move on, turn the idea into a small review drill. Pick one representative problem and write three things before you code: the pattern name, the data structure you expect to use, and the edge case that would make the naive version fail. After you solve it, rewrite the explanation in two sentences without looking at the code.
That last step is the difference between recognizing a solution and owning it. If you can explain why the approach works, you can usually rebuild it under pressure. If you only remember the final code shape, the next variant will feel like a new problem.
On AlgoArena, pair this with a timed rep only after the slow explanation is clean. Speed is useful when it compresses a skill you already understand. It is noisy when it hides the fact that the invariant was never clear.
One-session exercise
End with one mixed rep. Choose a problem where the pattern is present but not named in the title. Spend five minutes identifying the signal, ten minutes coding, and five minutes writing a post-solve note about what made the pattern recognizable. If you cannot name the signal before coding, the next best rep is not a harder problem. It is another example of the same pattern with different surface details.
That small debrief is what turns a guide into skill. You are training yourself to notice the shape before the solution is obvious.
Repeat the same exercise once with notes open and once with notes closed. The gap between those two attempts tells you whether the idea is still borrowed or has become part of your own toolkit.
If the closed-notes pass fails, keep the problem but shrink the scope: trace one loop, one recursive call, or one state transition until the reason is obvious.