Binary Search
Use sorted order to eliminate half of the remaining search space every step.
0 of 3 problems solved
Binary Search
Use sorted order to eliminate half of the remaining search space every step.
- •Is the array sorted?
- •Can I eliminate half the search space each step?
- •Do I update left or right based on mid comparison?
Binary Search is just disciplined guessing. Because the array is sorted, the middle value tells you which entire half cannot possibly contain the answer. That means every comparison deletes half the search space. You are not scanning faster. You are refusing to scan what you already know is useless.
The power comes from sorted order plus deleting half the problem every step.
- 1Track left and right boundaries.
- 2Pick the middle index.
- 3If nums[mid] is the target, return it.
- 4If nums[mid] is too small, move left past mid. If too large, move right before mid.
- 5Repeat until the search space disappears.
Updating the wrong boundary can create infinite loops or skip the answer. Every move must remove mid from the remaining search space.
Find Peak Element
Binary search: if mid is smaller than its right neighbor, a peak must lie to the right. Otherwise a peak exists at mid or to its left.
Median of Two Sorted Arrays
Binary search on the smaller array to find the partition where combined left halves have exactly half the total elements and no cross-boundary value violates order.