Chapter 11 — Binary Search (& Search on Answer
Chapter 11 — Binary Search (& Search on Answer)
Hey everyone! Welcome to Season 3 — Searching & Sorting!
Binary search is the most elegant O(log n) algorithm in all of DSA. The idea is almost magical: by repeatedly halving the search space, you can find an item among a billion sorted elements in about 30 steps. Master the exact template and you'll never write an off-by-one bug again.
What we will cover:
- Why binary search is O(log n)
- The exact template (no off-by-one bugs)
- First & last occurrence
- Search in a rotated sorted array
- "Binary search on the answer" — the advanced pattern
- Lower bound / upper bound
- Interview Questions
1. Why It's O(log n)
The one prerequisite: the data must be sorted. Each step you check the middle and throw away half the array.
┌─────────────────────────────────────────────────────────────┐ │ Searching 1,000,000,000 sorted items: │ │ │ │ 1 billion → 500M → 250M → ... → 1 │ │ That's only about 30 halvings → log₂(1e9) ≈ 30 steps! │ │ │ │ Linear search would take up to 1 billion steps. │ └─────────────────────────────────────────────────────────────┘
2. The Exact Template
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1; // inclusive bounds
while (lo <= hi) { // note: <=
const mid = lo + Math.floor((hi - lo) / 2); // avoids overflow
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1; // go right
else hi = mid - 1; // go left
}
return -1; // not found
}
THE 3 RULES THAT KILL OFF-BY-ONE BUGS: 1. Use lo <= hi (inclusive hi) 2. mid = lo + (hi - lo) / 2 (not (lo+hi)/2 — overflow safe) 3. Always move past mid: lo = mid + 1 OR hi = mid - 1
HAND TRACE: binarySearch([1,3,5,7,9,11], 7) lo=0 hi=5 → mid=2 (5) 5 < 7 → lo=3 lo=3 hi=5 → mid=4 (9) 9 > 7 → hi=3 lo=3 hi=3 → mid=3 (7) found! return 3 ✔
3. First & Last Occurrence
When duplicates exist, don't stop at the first match — keep searching one side to find the boundary.
function firstOccurrence(arr, target) {
let lo = 0, hi = arr.length - 1, ans = -1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) {
ans = mid;
hi = mid - 1; // keep looking LEFT for an earlier one
} else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
// For last occurrence: on a match, do lo = mid + 1 instead.
4. Search in a Rotated Sorted Array
A sorted array rotated at some pivot, e.g. [4,5,6,7,0,1,2]. One half is always still sorted — figure out which, then decide where to go.
function searchRotated(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
if (arr[lo] <= arr[mid]) { // LEFT half sorted
if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // RIGHT half sorted
if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
// Still O(log n)!
5. Binary Search on the Answer (Advanced)
The mind-bending pattern: sometimes you binary-search not over an array, but over the range of possible answers. If you can write a canDo(x) check that's monotonic (true past some threshold, false before), you can binary-search for that threshold.
┌─────────────────────────────────────────────────────────────┐ │ CLUE: "minimum/maximum value such that a condition holds" │ │ │ │ feasible: F F F F T T T T T │ │ ▲ │ │ find this boundary with binary search │ └─────────────────────────────────────────────────────────────┘
// Example shape: smallest capacity to ship packages in D days
function minCapacity(weights, days) {
let lo = Math.max(...weights); // can't be smaller than biggest item
let hi = weights.reduce((a, b) => a + b, 0); // all in one day
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (canShip(weights, days, mid)) hi = mid; // feasible → try smaller
else lo = mid + 1; // infeasible → go bigger
}
return lo;
}
6. Lower Bound / Upper Bound
| Term | Returns |
|---|---|
| Lower bound | First index with value >= target |
| Upper bound | First index with value > target |
These are the building blocks for "how many elements are < x?" and insertion-position questions.
Interview Questions — Quick Fire!
Q: What's the prerequisite for binary search and why?
"The data must be sorted. Binary search works by comparing the target to the middle element and discarding half the range; that decision is only valid if the elements are ordered."
Q: Why is binary search O(log n)?
"Each step halves the remaining search space. Starting from n elements, it takes about log₂(n) halvings to narrow down to one, so the time is O(log n). A billion elements need only about 30 comparisons."
Q: How do you avoid the mid-point overflow bug?
"Compute mid as lo + (hi - lo) / 2 instead of (lo + hi) / 2. Adding lo and hi can overflow in fixed-size integer languages; the subtraction form stays within bounds. In JS it's mostly a good-habit thing."
Q: How do you search a rotated sorted array in O(log n)?
"At each step one half is guaranteed to be sorted. Check which half is sorted by comparing arr[lo] and arr[mid], decide whether the target lies in that sorted half, and recurse into the correct half. It stays O(log n)."
Q: What is 'binary search on the answer'?
"When the answer is a value in a numeric range and there's a monotonic feasibility check — feasible above some threshold, infeasible below — you binary-search over the value range instead of an array. Classic for 'minimum capacity' or 'minimum time' optimization problems."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Prerequisite | Data must be sorted. |
| Complexity | O(log n) — halve each step. |
| Template | lo<=hi, mid=lo+(hi-lo)/2, always move past mid. |
| First/last | On match, keep searching one side. |
| Rotated array | One half is always sorted. |
| Search on answer | Binary-search the answer range via monotonic check. |
What's Next?
Chapter 12: Sorting Algorithms — bubble/selection/insertion (the O(n²) trio), then merge sort and quick sort (the O(n log n) champions), and why O(n log n) is the speed limit for comparison sorts.
Keep coding, keep grinding! See you in the next one!
Post a Comment