SearchMedium

Binary Search

Halve the search space each iteration on sorted or monotonic data.

How it works

Binary Search repeatedly halves the search space by comparing the target to the middle element. If target < mid, search the left half; if target > mid, search the right half; if equal, found it. The key insight is that this works on any monotonic function — not just sorted arrays. "Binary search on the answer" is a powerful technique: instead of searching for a value in an array, you search for the answer directly. Define a feasibility function canAchieve(x) that returns true/false, then binary search for the boundary. Common variants: (1) Find exact value. (2) Find leftmost/rightmost occurrence. (3) Find insertion point. (4) Binary search on answer range.

Interactive Playground

lo = 0, hi = 9. Search space is the entire sorted array.

Speed

When to use

Finding an element in a sorted array
Finding the boundary between valid/invalid answers
Minimize or maximize a value with a feasibility function

✅Tips

1Use `mid = left + (right - left) / 2` (integer division) to avoid integer overflow.

2Template for finding leftmost position: `while left < right`, move `right = mid` when condition is true.

3Template for finding rightmost position: move `left = mid + 1` when condition is false.

4Binary search on the answer: define the range [lo, hi] as the minimum and maximum possible answers, then binary search within it.

❌Common Mistakes

!Infinite loop when `mid = (left + right) / 2` rounds down — for rightmost search, use `mid = left + (right - left + 1) / 2`.

!Using `left <= right` for boundary search problems — this causes off-by-one; use `left < right` instead.

!Not checking if the array is actually sorted before applying Binary Search.

!Forgetting to handle the case where the target does not exist in the array.

💡 Key Insight:Ask "can I do better?" not "what is the answer?" — binary search on the answer.

Solved Problems0

No solved problems yet.