aloalgo.comBinary Search Beyond the Basics
Binary search looks simple, but getting it right under pressure is surprisingly tricky. Off-by-one errors, infinite loops, wrong boundary conditions... sound familiar? This guide will give you a rock-solid mental model that works every time.1. The Core Idea
Binary search finds a target in a sorted space by repeatedly halving the search range. But here's the key insight:Binary search doesn't just find elements—it finds boundaries.
Think of it as answering: "Where does the property change from false to true?"
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Value | 1 | 3 | 5 | 7 | 9 | 11 |
| ≥ 6? | F | F | F | T | T | T |
Binary search finds the boundary where F → T (index 3 in this case).
2. The Universal Template
Here's a template that handles almost every binary search variant:Key decisions explained:
left <= right: Use when searching for exact matchmid = left + (right - left) // 2: Prevents integer overflowleft = mid + 1andright = mid - 1: We've checked mid, exclude it
3. The Three Patterns
Most binary search problems fall into one of three patterns:Pattern 1: Find Exact Value
Idea: Compare the middle element with the target. If equal, return it. If target is smaller, search the left half. If larger, search the right half.- Time: O(log n)
- Space: O(1)
Pattern 2: Find First True (Lower Bound)
Find the first position where a condition becomes true. This is the most versatile pattern.Use cases:
- First element ≥ target (lower bound)
- First occurrence of target
- First false in [T,T,T,F,F,F]
- Minimum value that satisfies a condition
Pattern 3: Find Last True (Upper Bound)
Find the last position where a condition is true.Critical: Note
(right - left + 1) // 2 rounds up to avoid infinite loops when left = mid.4. Common Applications
First and Last Occurrence
Search in Rotated Array
The array was sorted, then rotated. One half is always sorted.Find Peak Element
A peak is greater than its neighbors. Binary search works because we can always move toward a "higher" side.Find Minimum in Rotated Array
5. Binary Search on Answer
Sometimes you're not searching an array—you're searching a range of possible answers. This is a powerful technique.Example: Minimum Days to Make Bouquets
Given bloom days and requirements, find the minimum days to make k bouquets.The pattern:
- Define the search space (min to max possible answer)
- Write a function to check if an answer works
- Binary search for the first/last valid answer
6. Avoiding Common Mistakes
| Mistake | Problem | Fix |
|---|---|---|
mid = (left + right) / 2 | Integer overflow | mid = left + (right - left) // 2 |
left = mid with floor division | Infinite loop | Use (right - left + 1) // 2 to round up |
| Wrong loop condition | Off-by-one or infinite loop | Use <= for exact, < for bounds |
| Not handling empty array | Index out of bounds | Check length before search |
| Wrong initial right bound | Missing edge cases | Use len(arr) for lower bound, len(arr)-1 for exact |
7. Quick Decision Guide
Which template to use?- Finding exact value: Use
<=loop,mid ± 1updates - Finding first ≥ target: Use
<loop,right = mid - Finding last ≤ target: Use
<loop,left = mid, round up - Finding minimum valid answer: Binary search on answer, find first true
- Finding maximum valid answer: Binary search on answer, find last true
8. Complexity
| Operation | Time | Space |
|---|---|---|
| Binary search (iterative) | O(log n) | O(1) |
| Binary search (recursive) | O(log n) | O(log n) |
| Binary search on answer | O(log(range) × check) | Depends on check |
9. Practice Problems
FundamentalsRotated ArraysAdvancedFinal Thoughts
Binary search mastery comes from understanding that you're always searching for a boundary—the point where a condition flips. Once you internalize this, the template variations become intuitive: you're just deciding which side of the boundary you want.Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.