1. One-Liner
Binary search finds a target in a sorted array by repeatedly cutting the search interval in half using the middle index.
2. The Problem It Solves
You have a sorted list (or can treat indices as ordered) and need to know whether a value exists and where, or the insertion point, without scanning every element. Linear scan is O(n); binary search is O(log n).
3. The Core Idea
Like looking up a word in a dictionary: open the middle; if your word is alphabetically before that page, search the left half; otherwise the right half. Each decision eliminates half of the remaining work.
4. How It Works (Step-by-Step)
| Step | Action |
|---|
| 1 | Set low = 0, high = n - 1. |
|---|
| 2 | While low <= high, compute mid = (low + high) // 2 (watch overflow in other languages). |
|---|
| 3 | If arr[mid] == target, return mid. |
|---|
| 4 | If arr[mid] < target, set low = mid + 1. |
|---|
| 5 | Else set high = mid - 1. |
|---|
| 6 | If the loop ends, the target is absent (return -1 or use low as insert position). |
|---|
5. Dry Run Example
Array: [1, 3, 5, 7, 9, 11], target: 7
| Iteration | low | high | mid | arr[mid] | Next |
|---|
| 1 | 0 | 5 | 2 | 5 | 7 > 5 → low = 3 |
|---|
| 2 | 3 | 5 | 4 | 9 | 7 < 9 → high = 3 |
|---|
| 3 | 3 | 3 | 3 | 7 | Found → index 3 |
|---|
6. Key Properties
| Property | Detail |
|---|
| Requires | Random-access, sorted order (or monotone predicate). |
|---|
| Stable variant | Lower/upper bound need careful mid handling. |
|---|
| Overflow | Prefer mid = low + (high - low) / 2 in C++/Java. |
|---|
7. Where It Is Used
| Company / domain | Use |
|---|
| Databases | B-tree internal search, index lookups. |
|---|
| Google / Meta | Sorted timelines, ranking thresholds, feature flags by version. |
|---|
| Games | Collision queries, LOD selection on sorted keys. |
|---|
8. Interview Tips
Interviewers expect correct boundaries (low <= high vs lower_bound patterns), overflow-safe mid, and O(log n) justification. Follow-ups: first/last occurrence, rotated sorted array, sqrt or predicate binary search on answer space.
9. Comparison with Other Algorithms
| Algorithm | When it wins vs binary |
|---|
| Interpolation | Uniformly distributed numeric keys → fewer probes. |
|---|
| Jump / Exponential | Special structures or unbounded/infinite arrays. |
|---|
| Linear | Tiny n or unsorted data (no sort cost). |
|---|
10. Complexity
| |
|---|
| -- | -- |
|---|
| Time | O(log n) comparisons |
|---|
| Space | O(1) iterative; O(log n) if recursive stack |
|---|
Implementation Example (PYTHON)
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1