Binary Search
Practice & Revision
Binary search pattern recognition decision tree, cheat sheet, and Top 15 must-solve binary search interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Binary Search. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Binary Search Decision Tree
Use this flow chart to determine which binary search variant fits your problem:
3. Revision Cheat Sheet
Template Quick-Reference Invariants
| Template | Loop Condition | Midpoint Calculation | Left Update | Right Update | Return Value |
|---|---|---|---|---|---|
| Exact Match | lo <= hi | lo + (hi - lo) / 2 | lo = mid + 1 | hi = mid - 1 | mid (or -1) |
| Left Boundary | lo < hi | lo + (hi - lo) / 2 | lo = mid + 1 | hi = mid | lo (insertion slot) |
| Right Boundary | lo < hi | lo + (hi - lo + 1) / 2 | lo = mid | hi = mid - 1 | lo (last occurrence) |
| Search on Answer | lo < hi | lo + (hi - lo) / 2 | lo = mid + 1 | hi = mid | lo (min value) |
4. Top 15 Must-Solve Binary Search Problems
5. Problem-Solving Framework
When faced with a binary search question, use this checklist:
1. Identify Monotonicity:
- If the output values must satisfy some property that increases or decreases continuously (e.g., higher capacity always works, lower capacity always fails), think Binary Search on Answer.
2. Verify Loop Termination:
- For exact matches, use lo <= hi.
- For boundary limits or minimum checks, use lo < hi and make sure your updates (hi = mid vs lo = mid + 1) don't skip elements.
3. Midpoint Overflow Protection:
- Always use mid = lo + (hi - lo) / 2 to avoid index issues.
6. Quiz
Question 1: When is a right boundary binary search midpoint rounded up (lo + (hi - lo + 1) / 2)?
Answer: If we do not round up, whenlo and hi differ by exactly 1 (e.g. lo = 3, hi = 4), the division truncates down (mid = 3). If arr[mid] is feasible, we set lo = mid (which is lo = 3), leading to an infinite loop since boundaries never change. Rounding up forces mid = 4, resolving the partition boundaries.
Question 2: What is the time complexity of searching in a rotated sorted array containing duplicates (e.g. [1, 0, 1, 1, 1])?
Answer:O(N) in the worst case. When arr[lo] == arr[mid] == arr[hi], we cannot tell which half is sorted. We must decrement both bounds (lo++, hi--) linearly until they differ, degrading logarithmic performance.
Question 3: How does Peak Finder binary search work if the array is unsorted?
Answer: Ifarr[mid] < arr[mid + 1], there must be at least one peak in the right half (since we are climbing). If arr[mid] > arr[mid + 1], there must be a peak in the left half. By comparing mid with its neighbor, we can choose a path even without global sorting.
Question 4: What is the search space range for the "Median of Two Sorted Arrays" problem?
Answer: We binary search on the partition index of the smaller array. Thus, the search space size is\min(N, M), yielding a fast O(log(\min(N, M))) running time.
Question 5: What is the output of lower_bound(6) for array [1, 3, 5, 7]?
Answer:3 (index of element 7), which is the first element greater than or equal to 6.