> ## Documentation Index > Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt > Use this file to discover all available pages before exploring further. # Binary Search Pattern > Master binary search for sorted arrays and optimization problems Binary Search Pattern ## What is Binary Search? **Binary Search** is a divide-and-conquer algorithm that repeatedly halves the search space. It reduces O(n) linear search to O(log n) by eliminating half the possibilities at each step. Imagine looking up a word in a physical dictionary. You would never start at page 1 and read every page. Instead, you open to the middle, decide if your word comes before or after that page, and repeat on the correct half. Each flip eliminates roughly half the remaining pages. That is binary search: a disciplined halving of possibilities. The key insight is that binary search does not require a "sorted array" specifically -- it requires a **monotonic predicate**. If you can define a condition that is `false` for all values below some threshold and `true` for all values above it (or vice versa), you can binary-search for that threshold. This generalization is what enables "binary search on the answer" for optimization problems, which is arguably the most common interview pattern. **Complexity**: O(log n) time, O(1) space. For a billion-element array, that is about 30 comparisons instead of a billion -- one of the most dramatic efficiency wins in all of computer science. **Quick Recognition**: If you see **"sorted array"** or need to **minimize/maximize** something with a feasibility check, Binary Search is likely the answer! ## Pattern Recognition Cheatsheet **Map keywords in the problem statement to the binary search variant. If you see one of these, reach for the matching template.** | Problem Keyword | Technique | Template to Reach For | | --------------------------------------------------------------------- | ------------------------------------------ | ------------------------------------------------------ | | "sorted array, find target" | Standard binary search | `left <= right`, return -1 if not found | | "find first occurrence", "leftmost", "lower bound", "insertion point" | Lower-bound search | `left < right`, `right = mid` when condition holds | | "find last occurrence", "rightmost", "upper bound" | Upper-bound search | `left < right`, condition uses strict greater | | "find peak element", "find a local max" | Compare mid with mid+1, walk uphill | `left < right`, halve toward larger neighbor | | "rotated sorted array", "minimum in rotated", "search in rotated" | Find which half is sorted, then decide | Standard template with extra branching | | "minimize the maximum X", "maximize the minimum X" | Binary search on the answer | Define monotonic predicate, search answer space | | "minimum capacity", "minimum time", "smallest divisor" | Binary search on the answer (minimization) | `left < right`, `right = mid` if feasible | | "largest possible X", "maximum K such that..." | Binary search on the answer (maximization) | `left < right`, ceiling mid + `left = mid` if feasible | | "search in 2D matrix" (rows AND cols sorted) | Staircase search from top-right | O(m+n), not binary search | | "search in 2D matrix" (each row sorted, rows chained) | Treat as 1D sorted, binary search | Flatten with row = mid / n, col = mid % n | | "median of two sorted arrays" | Binary search on partition position | Search smaller array's partition point | **Rule of thumb**: anything that says "minimum/maximum X such that Y holds" is binary search on the answer. Anything with explicit sorted input is standard or bounds. If the data is unsorted but has a monotonic property along an axis (peak finding, mountain arrays), it is still binary search. ## Universal Templates These three templates cover roughly 95% of binary search interview problems. The single most important insight: **pick a template and stick to it for that problem -- do not mix conventions.** ### Template 1: Exact Match (`left <= right`) Use when the answer is a specific element in a sorted array, and "not found" returns -1. ```python Python theme={null} def standard(arr, target): left, right = 0, len(arr) - 1 # closed interval [left, right] while left <= right: # search until interval is empty mid = left + (right - left) // 2 # overflow-safe midpoint if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 # exclude mid -- it is too small else: right = mid - 1 # exclude mid -- it is too big return -1 ``` ```java Java theme={null} int standard(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // overflow-safe if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ``` ```javascript JavaScript theme={null} function standard(arr, target) { let left = 0, right = arr.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ``` ```cpp C++ theme={null} int standard(vector& arr, int target) { int left = 0, right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // overflow-safe if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ``` ### Template 2: Lower Bound -- the canonical interview template (`left < right`) Use this for **first occurrence**, **insertion point**, **first element satisfying a predicate**, and **most "binary search on the answer" problems**. The convergence is `left == right == answer`. ```python theme={null} def lower_bound(arr, target): left, right = 0, len(arr) # right = len(arr), one past the end! while left < right: # converge until left == right mid = left + (right - left) // 2 # floor mid if arr[mid] < target: left = mid + 1 # mid is too small -- exclude else: right = mid # mid might be the answer -- KEEP return left # left == right == answer ``` **Why `left < right` and not `left <= right` here?** Because `right = mid` (not `mid - 1`) keeps `mid` in the range. If you used `left <= right` with `right = mid`, then when `left == right == mid`, the next iteration sets `right = mid` again -- no progress, infinite loop. **Why `left = mid + 1` and not `left = mid`?** Because mid was just shown to be too small (`arr[mid] < target`), so excluding it is safe. If you wrote `left = mid`, then at `left + 1 == right`, mid equals left, and you would loop forever. **The pattern is rigid**: `left < right`, floor mid, `right = mid` when condition holds, `left = mid + 1` when it does not. Memorize it. ### Template 3: Upper Bound (`left < right` with strict comparison) To find **first element strictly greater than target**: ```python theme={null} def upper_bound(arr, target): left, right = 0, len(arr) while left < right: mid = left + (right - left) // 2 if arr[mid] <= target: # <= instead of < left = mid + 1 else: right = mid return left ``` **Trick**: `last_occurrence(target) == upper_bound(target) - 1` (and verify the value matches). ### How to choose mid for upper-bound (when `left = mid` is needed) Some upper-bound flavors use `left = mid` instead of `left = mid + 1` (when you want mid to potentially be the answer in the increasing-from-left direction). In that case, you MUST use **ceiling division** for mid: ```python theme={null} mid = left + (right - left + 1) // 2 # ceiling -- biases toward right ``` Otherwise, when `left + 1 == right`, mid equals left, and `left = mid` makes no progress -- infinite loop. The ceiling shifts mid toward the right so the update always moves forward. This pattern is rare but appears in problems like "find the largest K such that condition" written with `left = mid`. **Caveats and Traps -- read these BEFORE you start coding.** 1. **Off-by-one between `left <= right` vs `left < right`.** Pick one and stick with it for that problem. Do NOT switch mid-coding. The most common bug is using `left <= right` with `right = mid` (instead of `right = mid - 1`) -- this can infinite-loop when `left == right == mid`. Match the loop condition to the update rule: closed interval (`<=`) goes with `mid +/- 1`; converging interval (`<`) goes with `right = mid`. 2. **`(left + right) / 2` overflow in Java/C++.** When `left` and `right` are both close to `INT_MAX`, the sum overflows to a negative number, producing a negative mid and an out-of-bounds crash. Always write `left + (right - left) / 2`. This was a real bug in Java's `Arrays.binarySearch` for nearly a decade until Joshua Bloch flagged it in 2006. In Python this is technically unnecessary (arbitrary-precision ints), but write it anyway -- it shows awareness and hardens you for non-Python languages. 3. **Binary search on the answer requires a monotonic predicate -- define it first.** Before writing any code, articulate: "If X works, does X+1 also work?" If yes, you can binary search for the smallest X. If the predicate is non-monotonic (multiple transitions between false and true), binary search converges to one transition and silently misses the others. When in doubt, plot the predicate over a few sample values to confirm. 4. **Forgetting to update `left` or `right`.** Every iteration must shrink the search space. If neither pointer changes, you have an infinite loop. Check that every branch of your if/else moves at least one pointer. 5. **Wrong initial bounds.** For lower bound, `right = len(arr)` (NOT `len(arr) - 1`) -- the answer might be "insert past the end." For "binary search on the answer" problems, set `left = minimum possible answer` and `right = maximum possible answer`. Setting `left = 0` when the minimum is 1 (e.g., Koko Eating Bananas) causes the feasibility check to receive zero and divide by zero. 6. **Confusing rotated-array index with sorted-array index.** When searching in a rotated array, do NOT assume `arr[left]` is the smallest -- after rotation, the smallest could be anywhere. Always check which half is sorted using `arr[left] <= arr[mid]` (the `=` matters for two-element subarrays where left == mid). 7. **Duplicates in rotated array degrade to O(n).** When `arr[left] == arr[mid] == arr[right]`, you cannot determine which half is sorted. The only safe move is `left += 1`. Worst case becomes O(n) for inputs like `[1,1,1,1,1,1,3,1,1]`. ## Pattern Recognition Checklist * Array is **sorted** (or has monotonic property) * Need O(log n) instead of O(n) * **Minimize/maximize** with feasibility check * Finding **transition point** where condition changes * Search space can be **halved** each step * Array is **unsorted** with no order * Need to find **all occurrences** * **Linear scan** is already O(n) and sufficient * No clear way to **eliminate half** ## When to Use Finding elements, insertion points, or bounds Finding transition points where condition changes Minimizing/maximizing values with feasibility check Rotated arrays, peak finding, matrix search ## Pattern Variations ### 1. Standard Binary Search Find exact target in sorted array. The loop invariant is: "the target, if it exists, is within `[left, right]`." When `left > right`, the interval is empty and the target does not exist. **Why `left + (right - left) // 2` instead of `(left + right) // 2`?** In Java/C++, `left + right` can overflow a 32-bit integer when both are large. The subtraction form avoids this. In Python it does not matter (arbitrary precision), but using the safe form is good habit. **Time: O(log n).** **Space: O(1).** ```python Python theme={null} def binary_search(arr, target): """Find target in sorted array, return index or -1""" left, right = 0, len(arr) - 1 while left <= right: # Loop while search interval is non-empty mid = left + (right - left) // 2 # Safe midpoint (avoids overflow) if arr[mid] == target: return mid # Found -- return index elif arr[mid] < target: left = mid + 1 # Target is in the right half else: right = mid - 1 # Target is in the left half return -1 # Exhausted the search space -- target not present ``` ```java Java theme={null} public int binarySearch(int[] arr, int target) { // Find target in sorted array, return index or -1 int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // Avoid overflow if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } ``` ```cpp C++ theme={null} int binarySearch(vector& arr, int target) { // Find target in sorted array, return index or -1 int left = 0, right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // Avoid overflow if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } ``` ### 2. Lower Bound (First Occurrence) Find the first index where `arr[i] >= target`. Notice two critical differences from standard search: (1) `right` starts at `len(arr)` (one past the end, because the answer might be "insert at the end"), and (2) the loop condition is `left < right` (not `<=`), because `left == right` means we have converged on the answer. When `arr[mid] >= target`, we do `right = mid` (not `mid - 1`) because `mid` itself might be the answer -- we cannot discard it. **Use this for**: finding insertion points, first occurrence of a value, first position meeting a condition. ```python Python theme={null} def lower_bound(arr, target): """Find first index where arr[i] >= target""" left, right = 0, len(arr) # Note: right = len(arr), not len(arr)-1 while left < right: # Converge until left == right mid = left + (right - left) // 2 if arr[mid] < target: left = mid + 1 # mid is too small -- exclude it else: right = mid # mid could be the answer -- keep it return left # left == right == first position where arr[i] >= target ``` ```java Java theme={null} public int lowerBound(int[] arr, int target) { // Find first index where arr[i] >= target int left = 0, right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; // Don't exclude mid, it could be answer } } return left; } ``` ```cpp C++ theme={null} int lowerBound(vector& arr, int target) { // Find first index where arr[i] >= target int left = 0, right = arr.size(); while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; // Don't exclude mid, it could be answer } } return left; } ``` ### 3. Upper Bound (Last Occurrence) Find the first index where `arr[i] > target`. This is the mirror image of lower bound: instead of `>=`, we use `>`. The only code difference is changing `<` to `<=` in the comparison -- but that single character changes the semantics entirely. **How it relates to lower bound**: `upper_bound(target)` is the same as `lower_bound(target + 1)` for integers. For finding the **last occurrence** of a value, compute `upper_bound(target) - 1` and verify that position holds the target. **Walked example**: `arr = [1, 3, 3, 3, 5, 7]`, target = 3. We want the first index where `arr[i] > 3`, which is index 4 (value 5). So `upper_bound = 4`. The last occurrence of 3 is at index `4 - 1 = 3`. **Use this for**: finding the last occurrence of a value (`upper_bound - 1`), counting occurrences (`upper_bound - lower_bound`), finding the range of equal elements. ```python Python theme={null} def upper_bound(arr, target): """Find first index where arr[i] > target""" left, right = 0, len(arr) while left < right: mid = left + (right - left) // 2 if arr[mid] <= target: left = mid + 1 else: right = mid return left ``` ```java Java theme={null} public int upperBound(int[] arr, int target) { // Find first index where arr[i] > target int left = 0, right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) { left = mid + 1; } else { right = mid; } } return left; } ``` ```cpp C++ theme={null} int upperBound(vector& arr, int target) { // Find first index where arr[i] > target int left = 0, right = arr.size(); while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) { left = mid + 1; } else { right = mid; } } return left; } ``` ### 4. Binary Search on Answer This is arguably the most important binary search pattern for interviews. Instead of searching for an element in an array, you search for the **optimal value** in a continuous answer space. The pattern always has three parts: 1. **Define the search space** -- what is the minimum and maximum possible answer? 2. **Write a feasibility function** -- given a candidate answer, can we satisfy the constraints? 3. **Binary search** on the answer space using the feasibility function as the monotonic predicate. **When to recognize it**: Any problem that says "minimize the maximum" or "maximize the minimum" is almost certainly binary search on the answer. **Time: O(n \* log(range))** where n is the cost of the feasibility check and range is the answer space size. ```python Python theme={null} def min_capacity_to_ship(weights, days): """Minimum ship capacity to ship all packages in given days""" def can_ship(capacity): """Feasibility check: can we ship everything in 'days' days?""" current_weight = 0 days_needed = 1 # At least one day is required for weight in weights: if current_weight + weight > capacity: days_needed += 1 # Start a new day current_weight = 0 current_weight += weight return days_needed <= days # SEARCH SPACE: smallest possible capacity is the heaviest package # (can't split a package), largest is shipping everything in one day. left = max(weights) right = sum(weights) while left < right: mid = left + (right - left) // 2 if can_ship(mid): right = mid # Feasible -- try an even smaller capacity else: left = mid + 1 # Not feasible -- need more capacity return left # Smallest feasible capacity ``` ```java Java theme={null} public int minCapacityToShip(int[] weights, int days) { // Minimum ship capacity to ship all packages in given days int left = 0, right = 0; for (int w : weights) { left = Math.max(left, w); right += w; } while (left < right) { int mid = left + (right - left) / 2; if (canShip(weights, mid, days)) { right = mid; // Try smaller capacity } else { left = mid + 1; // Need more capacity } } return left; } private boolean canShip(int[] weights, int capacity, int days) { int currentWeight = 0; int daysNeeded = 1; for (int weight : weights) { if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = 0; } currentWeight += weight; } return daysNeeded <= days; } ``` ```cpp C++ theme={null} bool canShip(vector& weights, int capacity, int days) { int currentWeight = 0; int daysNeeded = 1; for (int weight : weights) { if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = 0; } currentWeight += weight; } return daysNeeded <= days; } int minCapacityToShip(vector& weights, int days) { // Minimum ship capacity to ship all packages in given days int left = *max_element(weights.begin(), weights.end()); int right = accumulate(weights.begin(), weights.end(), 0); while (left < right) { int mid = left + (right - left) / 2; if (canShip(weights, mid, days)) { right = mid; // Try smaller capacity } else { left = mid + 1; // Need more capacity } } return left; } ``` ## Classic Problems **Problem**: Search for target in rotated sorted array. **Approach**: Find which half is sorted, determine if target is in that half. **Time**: O(log n) | **Space**: O(1) **Problem**: Find any peak element (greater than neighbors). **Approach**: Compare mid with mid+1, move towards the larger side. **Time**: O(log n) | **Space**: O(1) **Problem**: Search in row-wise and column-wise sorted matrix. **Approach**: Treat as 1D array or start from top-right corner. **Time**: O(log(m\*n)) or O(m+n) | **Space**: O(1) **Problem**: Minimum eating speed to finish all bananas in h hours. **Approach**: Binary search on answer with feasibility check. **Time**: O(n log m) | **Space**: O(1) **Problem**: Find median of two sorted arrays in O(log(m+n)). **Approach**: Binary search on partition point of smaller array. **Time**: O(log(min(m,n))) | **Space**: O(1) ## Search in Rotated Sorted Array A sorted array that has been rotated at some pivot (e.g., `[4,5,6,7,0,1,2]`) loses its global order but retains a useful property: at any midpoint, **at least one half is still sorted**. The trick is to determine which half is sorted, then check if the target falls within that sorted half. If it does, search there; otherwise, search the other half. **How to tell which half is sorted**: If `nums[left] <= nums[mid]`, the left half `[left..mid]` is sorted. Otherwise, the right half `[mid..right]` is sorted. The `<=` (not `<`) handles the case where `left == mid` (subarray of size 1 or 2). **Walked example**: nums = \[4,5,6,7,0,1,2], target = 0. left=0, right=6, mid=3 (value 7). Left half \[4,5,6,7] is sorted, but 0 is not in \[4,7], so search right. left=4, right=6, mid=5 (value 1). Right half \[1,2] is sorted, 0 is not in \[1,2], so search left. left=4, right=4, mid=4 (value 0). Found at index 4. **Edge case**: Duplicates break this approach because `nums[left] == nums[mid]` no longer tells you which half is sorted. With duplicates, the worst case degrades to O(n). The standard workaround is to skip duplicates: `if nums[left] == nums[mid]: left += 1; continue`. **Time: O(log n)** without duplicates. **Space: O(1).** ```python Python theme={null} def search_rotated(nums, target): """Search for target in rotated sorted array""" left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # Left half is sorted if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # Right half is sorted else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1 ``` ```java Java theme={null} public int searchRotated(int[] nums, int target) { // Search for target in rotated sorted array int left = 0, right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } // Left half is sorted if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } // Right half is sorted } else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } ``` ```cpp C++ theme={null} int searchRotated(vector& nums, int target) { // Search for target in rotated sorted array int left = 0, right = nums.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } // Left half is sorted if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } // Right half is sorted } else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } ``` ## Template Code ```python Python theme={null} # Template 1: Standard (find exact match) def binary_search_standard(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # Template 2: Lower bound (first >= target) def binary_search_lower(arr, target): left, right = 0, len(arr) while left < right: mid = left + (right - left) // 2 if arr[mid] < target: left = mid + 1 else: right = mid return left # Template 3: Binary search on answer def binary_search_answer(low, high, is_valid): while low < high: mid = low + (high - low) // 2 if is_valid(mid): high = mid else: low = mid + 1 return low ``` ```java Java theme={null} // Template 1: Standard (find exact match) public int binarySearchStandard(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } // Template 2: Lower bound (first >= target) public int binarySearchLower(int[] arr, int target) { int left = 0, right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } // Template 3: Binary search on answer public int binarySearchAnswer(int low, int high, Predicate isValid) { while (low < high) { int mid = low + (high - low) / 2; if (isValid.test(mid)) { high = mid; } else { low = mid + 1; } } return low; } ``` ```cpp C++ theme={null} // Template 1: Standard (find exact match) int binarySearchStandard(vector& arr, int target) { int left = 0, right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } // Template 2: Lower bound (first >= target) int binarySearchLower(vector& arr, int target) { int left = 0, right = arr.size(); while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } // Template 3: Binary search on answer int binarySearchAnswer(int low, int high, function isValid) { while (low < high) { int mid = low + (high - low) / 2; if (isValid(mid)) { high = mid; } else { low = mid + 1; } } return low; } ``` ## Common Mistakes **Avoid These Pitfalls:** 1. **Integer Overflow**: Use `mid = left + (right - left) / 2` instead of `(left + right) / 2`. This matters in Java/C++ where `int` is 32-bit. An overflow here silently produces a negative index, causing an ArrayIndexOutOfBoundsException. 2. **Infinite Loop**: Every iteration must change either `left` or `right`. If you write `right = mid` in a loop that uses `left <= right`, you risk an infinite loop when `left == right == mid`. Match your loop condition to your update rule: `left <= right` with `mid +/- 1`, or `left < right` with `right = mid`. 3. **Off-by-one errors**: The three templates have different loop conditions and different right-pointer initializations for a reason. Using `left <= right` when you should use `left < right` (or vice versa) is the most common source of off-by-one bugs. When in doubt, trace through a 2-element array on paper. 4. **Wrong boundary after search**: After the loop, `left` and `right` point to different things depending on the template. For lower bound, `left` is the answer. For standard search, the element was found inside the loop or does not exist. Always verify what `left` means when the loop exits. 5. **Confusing the three templates**: The standard search (`left <= right`), lower bound (`left < right`, `right = mid`), and upper bound (`left < right`, `left = mid + 1`) are distinct. Mixing patterns (e.g., using `right = mid - 1` in a lower-bound search) silently skips valid answers. ## Debugging Checklist When your Binary Search solution fails: Is `left = 0` and `right = len - 1` or `right = len`? Use `left <= right` for exact match, `left < right` for bounds. Use `left + (right - left) / 2` to avoid overflow. Is `mid` included or excluded? (`right = mid` vs `right = mid - 1`) What should be returned when element is not found? ## The Three Templates Understanding which template to use is crucial: | Template | Loop Condition | Use Case | After Loop | | ----------- | --------------- | ---------------- | ---------------------- | | Standard | `left <= right` | Find exact match | Return -1 if not found | | Lower Bound | `left < right` | First >= target | `left` is answer | | Upper Bound | `left < right` | First > target | `left` is answer | ## Complexity Quick Reference | Problem Type | Time | Space | Key Insight | | ----------------- | -------------- | ----- | --------------------- | | Standard search | O(log n) | O(1) | Exact match | | Lower/Upper bound | O(log n) | O(1) | First occurrence | | Search on answer | O(n log range) | O(1) | Feasibility check | | Rotated array | O(log n) | O(1) | Find sorted half | | Peak finding | O(log n) | O(1) | Compare with neighbor | ## Interview Problems by Company | Problem | Company | Key Concept | | ---------------------- | --------------- | ---------------- | | Binary Search | All | Basic template | | Search Insert Position | Amazon, Google | Lower bound | | First Bad Version | Meta, Microsoft | Boolean search | | Sqrt(x) | Amazon | Search on answer | | Valid Perfect Square | Google | Search on answer | | Problem | Company | Key Concept | | ---------------------------- | --------------- | -------------------- | | Search Rotated Array | All FAANG | Modified search | | Find Peak Element | Meta, Microsoft | Monotonic property | | Find First and Last Position | Amazon | Double binary search | | Search 2D Matrix | Google | Flattened search | | Koko Eating Bananas | Google | Search on answer | | Problem | Company | Key Concept | | --------------------------- | -------------- | -------------------- | | Median of Two Sorted Arrays | Google, Amazon | Partition search | | Split Array Largest Sum | Google | Search on answer | | Find in Mountain Array | Google | Peak + two searches | | Smallest Good Base | Google | Math + binary search | ## Interview Tips **Script for interviews:** 1. "Since the array is sorted, I can use Binary Search for O(log n) time." 2. "I'll maintain two pointers, left and right, representing the search space." 3. "At each step, I calculate mid and compare with target." 4. "Based on comparison, I eliminate half the search space." 5. "I repeat until I find the target or the space is exhausted." | Interviewer Says | You Should Think | | ---------------------------------------- | ------------------------ | | "Array is sorted" | Binary Search! | | "Can you do better than O(n)?" | Binary Search might work | | "Find minimum/maximum that satisfies..." | Binary Search on answer | | "Array is rotated" | Modified Binary Search | | "Find first/last occurrence" | Lower/Upper bound | Be ready for these follow-ups: * "What if there are duplicates?" → Use lower/upper bound * "What if array is rotated?" → Find sorted half first * "Can you do it without extra space?" → Binary Search is already O(1) space * "What about very large arrays?" → Binary Search scales well ## Worked LeetCode Problems These six problems span the full binary-search surface area: standard search, search in modified arrays, peak finding, and binary search on the answer. Drill these to instinct. ### LC 704 -- Binary Search (Easy) **Brute force**: linear scan. O(n). **Optimized**: standard binary search. O(log n) time, O(1) space. ```python theme={null} def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 ``` This is the warmup. If you cannot write it cleanly in 60 seconds, the rest of this chapter will not stick. ### LC 33 -- Search in Rotated Sorted Array (Medium) **Brute force**: linear scan. O(n) -- ignores the structure entirely. **Optimized**: at each step, determine which half is sorted, then check if target is inside that sorted half. O(log n). ```python theme={null} def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid # Determine which half is sorted if nums[left] <= nums[mid]: # left half is sorted if nums[left] <= target < nums[mid]: # target is in left half right = mid - 1 else: left = mid + 1 else: # right half is sorted if nums[mid] < target <= nums[right]: # target is in right half left = mid + 1 else: right = mid - 1 return -1 ``` **Why `nums[left] <= nums[mid]` and not strict `<`?** When `left == mid` (subarray of size 1 or 2), the "left half" is a single element and is trivially sorted. Strict `<` would misclassify it. ### LC 153 -- Find Minimum in Rotated Sorted Array (Medium) **Brute force**: linear scan. O(n). **Optimized**: binary search using the property that the minimum is the unique element smaller than its predecessor. O(log n). ```python theme={null} def findMin(nums): left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] > nums[right]: left = mid + 1 # min is to the right of mid else: right = mid # min is mid or to the left return nums[left] ``` **Why compare with `nums[right]` and not `nums[left]`?** Because `nums[left]` could be larger than `nums[right]` even after we have narrowed in. Comparing with `nums[right]` gives a clean signal: if `mid > right`, the rotation point (and min) lies strictly to the right. Otherwise, the min is at or before mid. ### LC 162 -- Find Peak Element (Medium) **Brute force**: linear scan, return any index where `nums[i] > nums[i+1]`. O(n). **Optimized**: binary search. The "uphill" direction always contains a peak (because boundaries are -infinity). O(log n). ```python theme={null} def findPeakElement(nums): left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] < nums[mid + 1]: left = mid + 1 # uphill to the right -- peak is there else: right = mid # uphill or flat to the left -- peak is there return left ``` **Key insight**: this is binary search on an unsorted array. The structure that enables it is monotonicity in the "uphill direction" plus the boundary guarantee. The problem promises `nums[-1] = nums[n] = -infinity`, which guarantees a peak exists. ### LC 410 -- Split Array Largest Sum (Hard) **Brute force**: try all ways to split the array into k subarrays. Exponential. **Optimized**: binary search on the answer. The answer space is `[max(nums), sum(nums)]`, and the predicate "can we split into at most k subarrays each with sum at most X?" is monotonic in X. ```python theme={null} def splitArray(nums, k): def can_split(max_sum): groups = 1 current = 0 for n in nums: if current + n > max_sum: groups += 1 current = n if groups > k: return False else: current += n return True left, right = max(nums), sum(nums) # smallest possible to largest possible while left < right: mid = left + (right - left) // 2 if can_split(mid): right = mid # mid works -- try smaller else: left = mid + 1 # mid too small -- need bigger return left ``` **Why `left = max(nums)`?** Because no matter how we split, every subarray's sum is at least the largest single element (we cannot break elements apart). Setting `left` lower makes `can_split` always return false for those values, wasting iterations. **Why `right = sum(nums)`?** Because the largest possible answer is "put everything in one subarray," which requires capacity equal to the total sum. ### LC 875 -- Koko Eating Bananas (Medium) **Brute force**: try every speed from 1 to max(piles). O(max(piles) \* n). **Optimized**: binary search on the answer. The predicate "can Koko finish at speed K within H hours?" is monotonic in K. ```python theme={null} def minEatingSpeed(piles, h): def can_finish(k): hours = 0 for p in piles: hours += (p + k - 1) // k # ceiling division -- avoid floats return hours <= h left, right = 1, max(piles) while left < right: mid = left + (right - left) // 2 if can_finish(mid): right = mid # this speed works -- try slower else: left = mid + 1 # too slow -- speed up return left ``` **Why `right = max(piles)` and not `sum(piles)`?** Because at speed `max(piles)`, Koko finishes the largest pile in 1 hour, and every smaller pile in 1 hour each, totaling at most n hours. Since the problem guarantees `n <= h`, this is always feasible. Using a tighter upper bound saves a few iterations. **Why ceiling division `(p + k - 1) // k` and not `math.ceil(p / k)`?** Floating-point division introduces precision errors that break the comparison at edge values. Integer ceiling division is exact and faster. ## Curated LeetCode List A focused grind list grouped by difficulty. Solve all of these and you have covered the full binary-search surface area at FAANG. | # | Problem | Difficulty | Pattern | Why It Matters | | ---- | ------------------------------------ | ---------- | ------------------------------ | -------------------------------------------- | | 704 | Binary Search | Easy | Standard template | The warmup -- master this in 60 seconds. | | 35 | Search Insert Position | Easy | Lower bound | Canonical lower-bound application. | | 278 | First Bad Version | Easy | Lower bound on boolean | Tests transition-point recognition. | | 69 | Sqrt(x) | Easy | Binary search on answer | Gateway to the "search on answer" pattern. | | 367 | Valid Perfect Square | Easy | Binary search on answer | Same skeleton as Sqrt. | | 374 | Guess Number Higher or Lower | Easy | Standard with API call | Tests minimizing API calls. | | 33 | Search in Rotated Sorted Array | Medium | Find sorted half | The classic rotated-array problem. | | 81 | Search in Rotated Sorted Array II | Medium | Rotated with duplicates | O(n) worst case -- know when. | | 153 | Find Minimum in Rotated Sorted Array | Medium | Compare with right boundary | Cleaner than LC 33 -- great warmup. | | 154 | Find Minimum in Rotated II | Hard | Duplicates handling | Same as 153 but with `right -= 1` on ties. | | 162 | Find Peak Element | Medium | Walk uphill | Binary search WITHOUT a sorted array. | | 34 | Find First and Last Position | Medium | Lower + upper bound | Tests both bound templates back to back. | | 74 | Search a 2D Matrix | Medium | Flatten to 1D | Mind the row/col index math. | | 240 | Search a 2D Matrix II | Medium | Staircase from top-right | NOT binary search -- O(m+n). | | 875 | Koko Eating Bananas | Medium | Binary search on answer | The canonical "search on answer" problem. | | 1011 | Capacity to Ship Packages | Medium | Binary search on answer | Same skeleton as Koko. | | 1482 | Minimum Days to Make Bouquets | Medium | Binary search on answer | Tests greedy feasibility check. | | 1539 | Kth Missing Positive Number | Easy | Lower bound on transformed | Tests creative predicate design. | | 4 | Median of Two Sorted Arrays | Hard | Binary search on partition | The hardest binary search problem. | | 410 | Split Array Largest Sum | Hard | Binary search on answer | "Minimize the maximum" -- canonical pattern. | | 668 | Kth Smallest in Multiplication Table | Hard | Binary search + count | Search-on-answer with non-trivial count. | | 719 | Find Kth Smallest Pair Distance | Hard | Binary search + sliding window | Search on distance values. | | 4 | Median of Two Sorted Arrays | Hard | Partition search | Truly hard; staff-level question. | **Suggested order**: 704 to 35 to 278 to 69 to 33 to 153 to 162 to 34 to 74 to 875 to 1011 to 1482 to 410 to 4. ## Interview Q\&A -- Senior-Level Walkthroughs **What interviewers are really testing:** Whether you understand lower bound and upper bound as distinct operations and can implement both correctly. Off-by-one errors are immediate and obvious here -- "almost right" fails the test cases. **Strong Answer Framework:** 1. Recognize that "first position" is lower bound and "last position" is upper bound minus 1. 2. Run two separate binary searches. Both use Template 2 (`left < right`). 3. After each search, validate that the returned index actually contains the target (otherwise the target is not present). 4. State complexity: O(log n) per search, O(log n) total. O(1) space. **Real LeetCode Example -- LC 34 (full code):** ```python theme={null} def searchRange(nums, target): if not nums: return [-1, -1] # First position: lower bound of target left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid # mid might be first occurrence first = left if first == len(nums) or nums[first] != target: return [-1, -1] # Last position: upper bound of target minus 1 left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 # everything at mid is consumed else: right = mid last = left - 1 # upper bound is one past, so subtract 1 return [first, last] ``` **Walkthrough for `nums = [5,7,7,8,8,10]`, target = 8:** * First search: looking for first index where `nums[i] >= 8`. Converges to index 3. * Second search: looking for first index where `nums[i] > 8`. Converges to index 5. Last = 5 - 1 = 4. * Result: `[3, 4]`. **Senior follow-up 1**: "Can you express both first and last using a single lower\_bound function?" Answer: yes. `last_occurrence(target) == lower_bound(target + 1) - 1`. This works because the first index strictly greater than target is one past the last occurrence. Java's `Collections.binarySearch` returns this directly via its return-value contract. **Senior follow-up 2**: "How do you count the number of occurrences in O(log n)?" Answer: `upper_bound(target) - lower_bound(target)`. The two searches run in O(log n), and subtracting two indices is O(1). This is much better than finding any occurrence and then linearly scanning, which is O(n) when all elements are equal. **Senior follow-up 3**: "If you also got the constraint 'no extra space at all,' how would your code change?" Answer: it would not -- both searches already use O(1) space. The recursion stack is not an issue because we wrote them iteratively. If asked to write it recursively, mention that recursion adds O(log n) stack space, which is technically not O(1). **Common Wrong Answers:** * "Find any occurrence with standard binary search, then scan left and right linearly." This is O(n) worst case (imagine an array of all equal values). * Mixing template conventions -- using `right = len(nums) - 1` with `right = mid`, which can infinite-loop or skip the answer. * Not validating that `nums[first] == target` after the first search. If target is absent, `first` points to where it would be inserted, not to an actual occurrence. **Further Reading:** * LC 34 (Find First and Last Position) -- the source problem. * LC 35 (Search Insert Position) -- pure lower bound. * LC 278 (First Bad Version) -- lower bound on a boolean predicate. **What interviewers are really testing:** Whether you can recognize "binary search on the answer" in a problem that does not mention sorting at all. This pattern appears in dozens of medium and hard problems; if you nail Koko, you can handle Capacity to Ship, Split Array Largest Sum, and Aggressive Cows. **Strong Answer Framework:** 1. Identify that the answer space (eating speed K) is monotonic: if Koko finishes at speed K, she also finishes at speed K+1. 2. Define the search bounds: `low = 1` (smallest meaningful speed), `high = max(piles)` (any speed at or above this finishes in n hours). 3. Define the feasibility check: at speed K, total hours needed is the sum of `ceil(pile / K)` for each pile. 4. Binary search using Template 2: when feasible, try smaller (`right = mid`); else go bigger (`left = mid + 1`). 5. State complexity: O(n log m) where n = piles count, m = max pile size. **Real LeetCode Example -- LC 875 (full code):** ```python theme={null} def minEatingSpeed(piles, h): def can_finish(k): hours = 0 for p in piles: hours += (p + k - 1) // k # ceiling division return hours <= h left, right = 1, max(piles) while left < right: mid = left + (right - left) // 2 if can_finish(mid): right = mid # this speed works else: left = mid + 1 # too slow -- speed up return left ``` **The mental model**: imagine plotting `can_finish(k)` for k = 1, 2, 3, .... The output is a step function that goes from `false, false, ..., false, true, true, ..., true`. Binary search finds the transition point -- the smallest k where the predicate flips to true. **Senior follow-up 1**: "What if Koko could eat from multiple piles in the same hour?" Answer: the feasibility check changes because there is no per-pile rounding. Total hours needed is `ceil(sum(piles) / k)`, a single calculation. The rest of the binary search structure stays the same. This actually makes the problem much easier -- you can solve it analytically as `k = ceil(sum(piles) / h)`. **Senior follow-up 2**: "Why use ceiling division `(p + k - 1) // k` instead of `math.ceil(p / k)`?" Answer: floating-point division introduces precision errors. For very large `p` and small `k`, the result `p / k` may not be exactly representable as a double, and `math.ceil` could return one off the correct answer in edge cases. Integer ceiling is exact, branch-free, and faster. **Senior follow-up 3**: "Generalize this pattern. Give two other problems that use the exact same structure." Answer: (1) Capacity to Ship Packages within D Days (LC 1011) -- search for minimum capacity, predicate is "can we ship in D days?". (2) Minimum Number of Days to Make M Bouquets (LC 1482) -- search for minimum days, predicate is "are at least M bouquets bloomable?". (3) Magnetic Force Between Two Balls (LC 1552) -- search for maximum minimum distance. **Common Wrong Answers:** * "Try every speed from 1 to max(piles) and find the smallest that works." This is O(max(piles) \* n), which is way too slow when max(piles) is up to 10^9. * Setting `left = 0` -- causes division by zero in the feasibility check. * Setting `right = sum(piles)` -- correct but loose, wastes iterations. `max(piles)` is the tight bound. * Using floating-point math in the feasibility check -- precision bugs at edge cases. **Further Reading:** * LC 875 (Koko Eating Bananas) -- the gateway problem. * LC 1011 (Capacity to Ship Packages) -- structurally identical. * LC 410 (Split Array Largest Sum) -- the "minimize the maximum" version. **What interviewers are really testing:** Your ability to identify the invariant that survives rotation (one half is always sorted) and handle the edge case where duplicates break that invariant. **Strong Answer Framework:** 1. Identify the key insight: after rotation, at least one half (`[left, mid]` or `[mid, right]`) is always sorted. 2. Determine which half is sorted by comparing `nums[left]` to `nums[mid]`. 3. Check if the target falls in the sorted half's range. If yes, search there; else search the other half. 4. For duplicates: when `nums[left] == nums[mid] == nums[right]`, you cannot tell which half is sorted -- shrink by one. 5. State complexity: O(log n) without duplicates, O(n) worst case with duplicates. **Real LeetCode Example -- LC 33 (full code):** ```python theme={null} def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[left] <= nums[mid]: # left half sorted if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: # right half sorted if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1 ``` **For LC 81 with duplicates** -- add a guard: ```python theme={null} def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return True if nums[left] == nums[mid] == nums[right]: left += 1 # cannot tell -- shrink right -= 1 elif nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return False ``` **Senior follow-up 1**: "Why does the `<=` in `nums[left] <= nums[mid]` matter?" Answer: when `left == mid` (subarray of size 1 or 2), the "left half" is a single element and is trivially sorted. Strict `<` would misclassify this case and send the search to the wrong half. The `=` ensures that single-element subarrays are correctly considered sorted. **Senior follow-up 2**: "Why does duplicates degrade to O(n)?" Answer: information-theoretically, when n-1 elements are equal and one is different, you cannot localize the different element with fewer than O(n) comparisons. Concretely, when `nums[left] == nums[mid] == nums[right]`, both halves look identical -- you cannot eliminate either with certainty. The only safe move is to shrink by one, leading to linear worst case. **Senior follow-up 3**: "Could you find the minimum element in a rotated sorted array using binary search?" Answer: yes -- LC 153. Compare `nums[mid]` with `nums[right]`. If `nums[mid] > nums[right]`, the minimum is strictly to the right of mid (`left = mid + 1`). Else the minimum is at or to the left of mid (`right = mid`). This is cleaner than LC 33 because there is only one comparison branch. **Common Wrong Answers:** * Trying to find the rotation point first, then doing two separate binary searches. Two passes when one suffices, and harder to get right. * Comparing `nums[mid]` with `nums[right]` instead of `nums[left]` (mixing conventions). Both work but you must pick one and be consistent. * Not handling the duplicates case in LC 81 -- the algorithm silently produces wrong results on `[1,1,3,1]` searching for 3. **Further Reading:** * LC 33 (Search in Rotated Sorted Array) -- the source. * LC 81 (Search in Rotated Sorted Array II) -- the duplicates variant. * LC 153 / 154 (Find Minimum in Rotated Sorted Array I/II) -- companion problems. **What interviewers are really testing:** Whether you can transform a selection problem into a binary search on partition points. This is the hardest binary search problem on LeetCode and a staff-level question. **Strong Answer Framework:** 1. Recognize that the median divides all elements into two equal-sized halves -- a "left half" and "right half" with the median straddling them. 2. Binary search for the partition point in the smaller array. The partition in the larger array is determined by it (the two partitions together must equal half the total). 3. The valid partition satisfies `max(left half) <= min(right half)`, specifically `A[i-1] <= B[j]` and `B[j-1] <= A[i]`. 4. Handle edge cases with sentinel values (-infinity and +infinity) when the partition is at an array boundary. 5. State complexity: O(log(min(m, n))) -- always search the smaller array. **Real LeetCode Example -- LC 4 (full code):** ```python theme={null} def findMedianSortedArrays(A, B): if len(A) > len(B): A, B = B, A # ensure A is shorter m, n = len(A), len(B) total = m + n half = (total + 1) // 2 # ceiling -- for both even and odd left, right = 0, m while left <= right: i = (left + right) // 2 # partition in A j = half - i # partition in B A_left = A[i - 1] if i > 0 else float('-inf') A_right = A[i] if i < m else float('inf') B_left = B[j - 1] if j > 0 else float('-inf') B_right = B[j] if j < n else float('inf') if A_left <= B_right and B_left <= A_right: # valid partition if total % 2 == 1: return max(A_left, B_left) else: return (max(A_left, B_left) + min(A_right, B_right)) / 2 elif A_left > B_right: right = i - 1 # partition in A is too far right else: left = i + 1 # partition in A is too far left ``` **Why search the smaller array?** Because `j = half - i` must be in `[0, n]`. If we search the larger array, `j` could go negative for small `i` values, requiring extra bounds checking. Searching the smaller guarantees `j` stays valid. **Senior follow-up 1**: "Why use `(total + 1) // 2` for half?" Answer: this works for both odd and even total length. For total = 5 (odd), half = 3, and the median is the maximum of the left halves. For total = 6 (even), half = 3, and the median is the average of max-of-lefts and min-of-rights. The `+1` ensures the left half has the extra element when total is odd. **Senior follow-up 2**: "Generalize to find the kth smallest across two sorted arrays." Answer: change `half` from `(total + 1) // 2` to `k`. The same partition-search structure finds where exactly k elements are in the combined left halves. Complexity stays O(log(min(m, n))). **Senior follow-up 3**: "What if there are more than two arrays?" Answer: this exact partition technique does not extend cleanly. For K sorted arrays, use a min-heap of one element per array (O(k log k) for the median, or O(N log K) to fully merge). The two-array partition trick relies on a single binary-search axis that breaks down with more arrays. **Common Wrong Answers:** * "Merge the two arrays and find the median." O(m + n) -- works but does not satisfy the O(log) requirement. * Searching the larger array instead of the smaller -- invalid `j` indices for boundary cases. * Not using sentinel infinities for boundary partitions -- causes index-out-of-bounds errors. **Further Reading:** * LC 4 (Median of Two Sorted Arrays) -- the source, rated Hard. * "Median of Two Sorted Arrays" by Loïc Olive -- the cleanest derivation I have seen. * CLRS chapter 9 on selection algorithms. ## Practice Problems | Problem | Difficulty | Link | | ------------------------------ | ---------- | ---------------------------------------------------------------------------- | | Binary Search | Easy | [LeetCode 704](https://leetcode.com/problems/binary-search/) | | Search Insert Position | Easy | [LeetCode 35](https://leetcode.com/problems/search-insert-position/) | | Search in Rotated Sorted Array | Medium | [LeetCode 33](https://leetcode.com/problems/search-in-rotated-sorted-array/) | | Find Peak Element | Medium | [LeetCode 162](https://leetcode.com/problems/find-peak-element/) | | Median of Two Sorted Arrays | Hard | [LeetCode 4](https://leetcode.com/problems/median-of-two-sorted-arrays/) | ## Practice Roadmap * Solve: Binary Search, Search Insert Position * Focus: Master the basic template perfectly * Solve: Find First and Last Position, First Bad Version * Focus: Lower bound vs upper bound * Solve: Search in Rotated Array, Find Peak Element * Focus: Finding the sorted half * Solve: Koko Eating Bananas, Capacity To Ship * Focus: Binary search on the result space **Interview Tip**: When you see "sorted array" or "minimize/maximize" with a feasibility check, think Binary Search immediately. ## Interview Questions **What interviewers are really testing:** Whether you understand machine-level integer representation and have been bitten by subtle bugs in production, or you just memorized a template without knowing why each line exists. **Strong Answer:** * **The core issue is integer overflow.** When `left` and `right` are both large values close to `Integer.MAX_VALUE` (2^31 - 1 in Java/C++), adding them together exceeds the 32-bit signed integer range, wrapping around to a negative number. `mid` then becomes negative, causing an array-out-of-bounds crash or an infinite loop. * **`left + (right - left) / 2` avoids this** because `right - left` is always non-negative and smaller than `right`, so the intermediate value never overflows. * **In Python this is technically unnecessary** because Python has arbitrary-precision integers. But you should still write it this way in interviews to show awareness, and because real systems often involve C/C++/Java/Rust where it matters. * **Real-world example:** This was famously a bug in the Java standard library's `Arrays.binarySearch` for nearly a decade (reported by Joshua Bloch in 2006). The JDK shipped with `(left + right) / 2` and it only manifested on arrays with over a billion elements. * **Alternatively**, some people write `(left + right) >>> 1` (unsigned right shift) in Java, which also works because it treats the overflow bit correctly. But `left + (right - left) / 2` is clearer and portable. * **Complexity:** This is a constant-time operation either way; it does not change the O(log n) time or O(1) space complexity. **Red flag answer:** "I just always write it that way because the template says so" or "Both are the same thing." If you cannot explain *when* the naive version breaks, you are pattern-matching without understanding. **Follow-ups:** 1. "If Python handles big integers natively, can you name a language or environment where this bug would actually crash your program?" (Tests whether the candidate has written binary search outside of LeetCode, in C++/Java/Rust.) 2. "What is the unsigned right shift operator `>>>` in Java and why does it fix this problem?" (Tests bit-level understanding of two's complement representation.) **What interviewers are really testing:** Whether you truly understand binary search invariants or just memorized one template. This is the single most common source of off-by-one bugs. A candidate who can articulate this clearly almost certainly understands binary search deeply. **Strong Answer:** * **`while (left <= right)` is for exact-match searches.** The search space is `[left, right]` (closed interval). Every iteration either finds the target and returns, or shrinks the interval by moving `left = mid + 1` or `right = mid - 1`. When `left > right`, the space is empty and the target does not exist. * **`while (left < right)` is for boundary/bound searches** (finding the first element that satisfies a condition). The search space is `[left, right)` or you converge `left == right` to a single answer. You typically do `right = mid` (not `mid - 1`) because `mid` itself might be the answer. * **The gotcha with `left < right`:** if you accidentally write `right = mid - 1`, you may skip the answer. If you accidentally write `left = mid` (without `+ 1`), you get an infinite loop when `left + 1 == right` because `mid` equals `left` and nothing changes. * **My mental model:** `left <= right` means "I am still searching and have not found it yet." `left < right` means "I am narrowing down to a single candidate." * **Time/Space:** Both are O(log n) time, O(1) space. The difference is purely in correctness, not performance. **Red flag answer:** "I always use `left <= right`" or inability to explain what happens when you mix the wrong loop condition with the wrong pointer update. This signals the candidate will produce subtle bugs on boundary problems. **Follow-ups:** 1. "Write a binary search that finds the leftmost occurrence of a target in a sorted array with duplicates. Which template do you use and why?" (Tests whether they can convert the conceptual understanding into code on the spot.) 2. "If I use `while (left < right)` but write `left = mid` instead of `left = mid + 1`, what exactly happens? Walk me through a concrete two-element array." (Tests ability to trace through code and identify infinite loops.) **What interviewers are really testing:** This is the classic "modified binary search" problem. The interviewer wants to see if you can identify which half is sorted, reason about invariants under a twist, and handle edge cases (rotation at different points, duplicates, single-element arrays). It separates people who understand binary search from people who memorized it. **Strong Answer:** * **Key insight:** Even though the array is rotated, at least one half (left or right of `mid`) is always sorted. We can determine which half is sorted by comparing `nums[left]` with `nums[mid]`. * **Algorithm:** 1. Compute `mid`. If `nums[mid] == target`, return. 2. If `nums[left] <= nums[mid]`, the left half is sorted. Check if `target` falls in `[nums[left], nums[mid])`. If yes, search left; otherwise search right. 3. Else the right half is sorted. Check if `target` falls in `(nums[mid], nums[right]]`. If yes, search right; otherwise search left. * **Why `<=` and not `<` in the check?** When `left == mid` (two-element subarray), the left "half" is just one element and is trivially sorted. Using `<` would incorrectly classify it and send you to the wrong half. * **Edge cases to mention:** Array of size 1, array not rotated at all (rotation by 0), target not present, all elements equal. * **Complexity:** O(log n) time, O(1) space. However, if duplicates are allowed (LeetCode 81 variant), worst case degrades to O(n) because you cannot determine which half is sorted when `nums[left] == nums[mid] == nums[right]`. **Red flag answer:** Suggesting to "find the pivot first, then do two binary searches." While technically correct, it is an unnecessary two-pass approach. The single-pass approach shows deeper understanding. Also a red flag: not mentioning the duplicate edge case when asked. **Follow-ups:** 1. "What changes if the rotated array contains duplicates? What is the new worst-case time complexity and why?" (Tests awareness of the O(n) degenerate case and how to handle `nums[left] == nums[mid]`.) 2. "Could you find the rotation point (minimum element) using binary search? How does that relate to this problem?" (Tests whether the candidate sees the connection between finding the pivot and the search problem.) **What interviewers are really testing:** This is the single most important binary search concept for medium-to-hard interview problems. Many candidates only think of binary search as "search in a sorted array." The interviewer wants to see if you can recognize the broader pattern: binary searching over a monotonic solution space. **Strong Answer:** * **The core idea:** Instead of searching for a target in an array, you binary search over the space of possible answers. For each candidate answer, you run a feasibility check (a greedy O(n) function) to determine if that answer works. Since the feasibility function is monotonic (if capacity X works, then X+1 also works), binary search applies. * **Template:** Define `low` = minimum possible answer, `high` = maximum possible answer. Binary search: if `is_feasible(mid)`, try smaller (`high = mid`); else go bigger (`low = mid + 1`). Return `low`. * **When to use it:** * "What is the **minimum** capacity/speed/value such that \[condition]?" * "What is the **maximum** X such that \[condition]?" * Any problem where brute-forcing all possible answers is too slow but checking one answer is fast. * **Classic examples:** Koko Eating Bananas (minimum speed), Capacity to Ship Packages (minimum capacity), Split Array Largest Sum (minimize the maximum subarray sum), Aggressive Cows (maximize minimum distance). * **The hardest part** is defining the search space bounds correctly. For "minimum capacity to ship," `low = max(single_weight)` (you must be able to carry the heaviest item) and `high = sum(all_weights)` (ship everything in one day). * **Complexity:** O(n log R) where R is the range of the answer space and n is the cost of the feasibility check. Space is O(1). **Red flag answer:** Only being able to describe binary search on arrays and not recognizing this pattern. Or defining the search bounds incorrectly (e.g., `low = 0` instead of `low = max(weights)` in the shipping problem, which would make the feasibility check fail for impossible capacities). **Follow-ups:** 1. "In the 'Split Array Largest Sum' problem, you need to minimize the maximum subarray sum when splitting into k parts. Walk me through how you would set up the binary search bounds and the feasibility check." (Tests whether the candidate can apply the pattern to a new problem in real time.) 2. "What happens if the feasibility function is not monotonic? Can you still use binary search on the answer? Give an example." (Tests deep understanding of the monotonicity requirement. Answer: No, binary search requires that if `f(x)` is true, then `f(x+1)` is also true for the minimization direction.) **What interviewers are really testing:** This is arguably the hardest binary search problem on LeetCode (Problem 4, rated Hard). The interviewer is testing whether you can transform a selection problem into a binary search on partition points, handle edge cases with infinities, and reason about even/odd total lengths. This is a staff-level question. **Strong Answer:** * **Key insight:** The median divides all elements into two equal halves. Instead of merging the arrays (O(m+n)), we binary search for the correct partition point in the smaller array and derive the other partition from it. * **Setup:** Let A be the smaller array (length m), B the larger (length n). We binary search `i` in `[0, m]` representing how many elements from A go in the left half. Then `j = (m + n + 1) / 2 - i` elements from B go in the left half. * **Invariant:** For a valid partition, `A[i-1] <= B[j]` and `B[j-1] <= A[i]`. If `A[i-1] > B[j]`, `i` is too big (move left). If `B[j-1] > A[i]`, `i` is too small (move right). * **Edge cases:** When `i = 0` or `i = m`, there are no elements on one side from A, so use negative/positive infinity for comparisons. Same for `j = 0` or `j = n`. * **Result:** If total length is odd, median is `max(A[i-1], B[j-1])`. If even, median is `(max(A[i-1], B[j-1]) + min(A[i], B[j])) / 2`. * **Complexity:** O(log(min(m,n))) time, O(1) space. We always binary search the smaller array to minimize iterations. **Red flag answer:** Suggesting O(m+n) merge as the solution (that is brute force, not what is asked). Or not knowing to binary search the smaller array. Or getting confused about the partition invariant and not being able to explain why `(m + n + 1) / 2` handles both even and odd cases. **Follow-ups:** 1. "Why do we specifically binary search the smaller array and not the larger one? What changes if we searched the larger array?" (Tests understanding that searching the smaller array guarantees `j` stays non-negative, avoiding invalid indices.) 2. "How would you extend this approach to find the kth smallest element across two sorted arrays instead of the median?" (Tests generalization ability. Answer: adjust the partition sizes so the left half contains exactly k elements.) **What interviewers are really testing:** Whether you can apply binary search to a problem that does not involve a sorted array. This tests your understanding of the deeper principle: binary search works on any space where you can eliminate half at each step, not just sorted data. Many candidates cannot see past "sorted array = binary search." **Strong Answer:** * **A peak element is one that is greater than its neighbors.** The problem guarantees `nums[-1] = nums[n] = -infinity` (boundary elements are smaller than everything), which guarantees at least one peak exists. * **Why binary search works here:** Compare `nums[mid]` with `nums[mid + 1]`. If `nums[mid] < nums[mid + 1]`, the right side is increasing, so a peak must exist to the right (either `mid + 1` is the peak or values eventually decrease, creating a peak). Move `left = mid + 1`. Otherwise, the left side (including `mid`) contains a peak. Move `right = mid`. * **The key insight is the "mountain guarantee":** because boundaries are `-infinity`, any increasing direction must eventually come back down, guaranteeing a peak. This is why we can safely discard half the array. * **Template:** Use `while (left < right)` with `right = mid` (not `mid - 1`), because `mid` itself could be the peak. When `left == right`, that index is the answer. * **Complexity:** O(log n) time, O(1) space. We do not find *the highest* peak, just *any* peak, which is sufficient. **Red flag answer:** "You cannot use binary search on an unsorted array" (wrong, and shows rigid thinking). Or describing an O(n) linear scan (correct but misses the point of the question). Or using `left <= right` with `right = mid - 1`, which can skip the peak. **Follow-ups:** 1. "What if I asked you to find a peak in a 2D matrix where a peak is greater than all four neighbors? Can you do better than O(m\*n)?" (Tests ability to extend the concept. Answer: O(m log n) or O(n log m) by applying peak finding on rows/columns iteratively.) 2. "Does this algorithm always find the global maximum? Why or why not?" (Answer: No. It finds *a* local peak. The global maximum would require O(n) in the worst case since the array is unsorted.) **What interviewers are really testing:** Whether you understand lower bound and upper bound as distinct operations and can implement both correctly without mixing up the boundary conditions. This is a fundamental test of binary search precision. Getting it "almost right" is not good enough here because off-by-one errors surface immediately. **Strong Answer:** * **Run two separate binary searches:** one to find the leftmost occurrence (lower bound) and one to find the rightmost occurrence. * **For the leftmost (lower bound):** Use `while (left < right)`. When `arr[mid] >= target`, set `right = mid` (keep searching left, `mid` might be the first). When `arr[mid] < target`, set `left = mid + 1`. After the loop, check if `arr[left] == target`. * **For the rightmost (upper bound):** Use `while (left < right)`. When `arr[mid] <= target`, set `left = mid + 1` (keep searching right). When `arr[mid] > target`, set `right = mid`. After the loop, `left - 1` is the last position. Alternatively, you can use `mid = left + (right - left + 1) / 2` (ceiling division) with `left = mid` to avoid infinite loops. * **Alternatively, for the rightmost**, find the upper bound (first element > target) and subtract 1. This is often cleaner: `upper_bound(target) - 1`. * **Edge cases:** target not in the array at all (return `[-1, -1]`), all elements are the target, target is at the boundaries. * **Complexity:** O(log n) time for each search, so O(log n) total. O(1) space. Much better than finding target and then linearly expanding outward, which is O(n) in the worst case when all elements are equal. **Red flag answer:** "Find any occurrence then scan left and right." This is O(n) worst case (imagine an array of all identical elements). It shows the candidate does not understand the point of binary search for bounds. Another red flag: only implementing one of the two correctly and hand-waving the other. **Follow-ups:** 1. "Can you express 'find first occurrence' and 'find last occurrence' both using a single lower\_bound function with different arguments?" (Tests deeper abstraction: last occurrence of `x` equals `lower_bound(x+1) - 1`.) 2. "How would you count the total number of occurrences of target in O(log n)?" (Answer: `upper_bound(target) - lower_bound(target)`. Tests whether they can compose the primitives.) **What interviewers are really testing:** This is a deceptively simple problem that tests whether you can recognize the "transition point" pattern: a sorted boolean space where values go from `false` to `true`, and you need the boundary. The interviewer also wants to see if you handle the API call count concern (minimizing calls to `isBadVersion`, which might be expensive). **Strong Answer:** * **This is a textbook lower-bound binary search** on a boolean predicate. The "array" is conceptually `[false, false, ..., false, true, true, ..., true]`. We need the first `true`. * **Use `while (left < right)` with `right = mid`** (not `mid - 1`) because `mid` could be the first bad version. If `isBadVersion(mid)` is true, the answer is `mid` or earlier. If false, the answer is after `mid`, so `left = mid + 1`. * **Why `left <= right` is wrong here:** It would require a separate variable to track the answer and extra logic, making the code messier. The `left < right` template naturally converges to the exact transition point. * **API call count:** Exactly `ceil(log2(n))` calls. For n = 1 billion, that is about 30 calls. If `isBadVersion` is a network call (e.g., checking a remote CI system), this efficiency matters. * **Complexity:** O(log n) time, O(1) space. **Red flag answer:** Linear scan from version 1 to n (O(n) calls). Or using `left <= right` with `right = mid - 1` and not tracking the answer separately, which would skip the first bad version. **Follow-ups:** 1. "What if `isBadVersion` is flaky and sometimes returns incorrect results? How would you make your search robust?" (Tests real-world thinking. Answer: call it multiple times per version and take majority vote, or use a probabilistic approach, accepting O(log n \* k) calls for k repetitions.) 2. "What if instead of a linear version history, versions form a DAG (like git commits with branches and merges)? How would you find the first bad commit?" (Tests ability to generalize beyond arrays. This is essentially `git bisect`, which handles DAGs by linearizing the commit history.) **What interviewers are really testing:** Whether you can recognize "binary search on the answer" in a problem that does not mention arrays or sorting at all. This is the gateway problem for the entire "binary search on answer" category. If you nail this, you can handle Capacity to Ship, Split Array Largest Sum, and Aggressive Cows. **Strong Answer:** * **Problem recap:** Koko has `n` piles of bananas. She eats at speed `k` bananas/hour (one pile at a time, rounds up partial hours). Find the minimum `k` to finish all piles in `h` hours. * **Why binary search applies:** The answer space `k` is monotonic. If Koko can finish at speed `k`, she can definitely finish at speed `k+1`. So we binary search for the smallest `k` where `can_finish(k, h)` is true. * **Search bounds:** `low = 1` (minimum meaningful speed), `high = max(piles)` (eating the largest pile in one hour means she finishes everything in n hours, and n \<= h is guaranteed by constraints). * **Feasibility check `can_finish(k, h)`:** For each pile `p`, the hours needed are `ceil(p / k)`. Sum all hours. If total \<= h, return true. The `ceil` can be computed as `(p + k - 1) / k` using integer math to avoid floating-point issues. * **Template:** `while (low < high)`, if `can_finish(mid)` then `high = mid`, else `low = mid + 1`. Return `low`. * **Complexity:** O(n log m) where n = number of piles, m = max pile size. The feasibility check is O(n), and we run it O(log m) times. Space is O(1). **Red flag answer:** Trying to sort the piles (irrelevant and wastes time). Or setting `high = sum(piles)` instead of `max(piles)` (technically still correct but shows lack of tight bound reasoning). Or using floating-point division in the feasibility check (introduces precision bugs). **Follow-ups:** 1. "What if Koko can eat from multiple piles in the same hour (no restriction of one pile per hour)? How does the feasibility check change?" (Tests ability to modify the greedy check. Answer: total bananas / k gives exact hours needed since no per-pile rounding.) 2. "Can you generalize this pattern? Give me two other problems that use the exact same structure." (Tests pattern recognition. Good answers: Capacity to Ship Packages within D Days, Minimum Number of Days to Make m Bouquets, Magnetic Force Between Two Balls.) **What interviewers are really testing:** There are multiple valid approaches with different trade-offs, and the interviewer wants to see if you can analyze all of them and pick the right one for the given constraints. This also tests whether you can exploit structure beyond "flat sorted array" for binary search. **Strong Answer:** * **Clarify which type of sorted matrix:** There are two common variants. * **Variant 1 (LeetCode 74):** Each row is sorted, and the first element of each row is greater than the last element of the previous row. The entire matrix is one sorted sequence. * **Variant 2 (LeetCode 240):** Each row is sorted left-to-right and each column is sorted top-to-bottom, but rows are NOT chained. This is the more interesting problem. * **For Variant 1:** Treat it as a 1D sorted array of size `m * n`. Binary search with index mapping: `row = mid / n`, `col = mid % n`. Time: O(log(m\*n)), Space: O(1). * **For Variant 2 (the staircase search):** Start from the top-right corner. If the current value equals target, return true. If it is greater than target, move left (eliminate that column). If it is less, move down (eliminate that row). Each step eliminates a row or column. * **Why top-right (or bottom-left)?** These corners give you a decision point: one direction increases values, the other decreases. Top-left and bottom-right do not have this property (both directions increase or both decrease). * **Complexity:** Variant 1: O(log(m\*n)) time. Variant 2: O(m + n) time. Both use O(1) space. * **Can you beat O(m+n) for Variant 2?** Yes, with binary search on each row: O(m log n). Or with a more advanced approach: binary search on the diagonal and then recurse on submatrices for O(m log(2n/m)) when m \< n. But the staircase approach is almost always sufficient and much simpler. **Red flag answer:** Only knowing the 1D flattening approach and not the staircase search (or vice versa). Or starting from the top-left corner and not being able to explain why it does not work. Or claiming O(log(m\*n)) for Variant 2 without recognizing it has weaker sorting guarantees. **Follow-ups:** 1. "If I only need to check existence, the staircase approach is O(m+n). But what if I need to count all elements less than a target? Can the staircase approach help?" (Tests creative adaptation. Answer: Yes, walk the staircase and sum up column counts as you go, still O(m+n).) 2. "What if the matrix is very tall (m >> n)? Which approach becomes better and why?" (Tests complexity analysis. When m >> n, binary search per row O(m log n) might lose to staircase O(m + n) since n is small. But if m >> n and you can search columns, O(n log m) beats both.) ## Interview Deep-Dive **Strong Answer:** * **Recognition signal:** The answer space is ordered (integers or real numbers), and the feasibility function is **monotonic** -- if X works, then X+1 also works (for minimization). This means there is a clean boundary between "does not work" and "works," and binary search finds that boundary. * **The three things you must define:** 1. **Search bounds (low and high).** Low = the smallest possible answer. High = the largest possible answer. Getting these wrong means you either miss the answer or search an unnecessarily large range. For "minimum speed to eat bananas in H hours": low = 1, high = max(piles). For "minimum capacity to ship packages in D days": low = max(weights), high = sum(weights). 2. **Feasibility function is\_feasible(mid).** This is typically a greedy O(n) function that checks whether the candidate answer `mid` satisfies the constraint. For bananas: sum of ceil(pile/mid) for each pile, check if total hours is within H. For shipping: greedily pack items into days, check if days needed is within D. 3. **Loop template and convergence.** Use `while low < high`, with `high = mid` when feasible (try smaller) and `low = mid + 1` when not. Return `low`. This converges to the smallest feasible value. * **Common mistake:** Setting `low` too low (e.g., low = 0 when the minimum meaningful answer is 1) causes the feasibility function to receive invalid inputs (division by zero for speed problems). * **Complexity:** O(n \* log(range)) where n is the cost of the feasibility check and range = high - low. For integer answers, log(range) is typically 30-40 iterations. **Follow-up: What if the feasibility function is not monotonic? Can you still use binary search?** * No. Binary search requires that the predicate transitions from false to true (or vice versa) exactly once. If there are multiple transitions, binary search will converge to one transition and miss the others. * If the function is non-monotonic, you need either linear search, ternary search (for unimodal functions), or a completely different approach. **Strong Answer:** * **Template 1 (exact match):** `while left <= right`, updates `left = mid + 1` and `right = mid - 1`. Search space is closed interval `[left, right]`. Returns inside the loop when found, or -1 after the loop. * **Template 2 (lower bound / first true):** `while left < right`, updates `left = mid + 1` and `right = mid`. Search space converges to a single point. `mid` itself might be the answer, so we keep it in the range with `right = mid`. * **Template 3 (upper bound / last true):** `while left < right`, updates `left = mid` and `right = mid - 1`. Requires ceiling division for mid: `mid = left + (right - left + 1) / 2` to avoid infinite loops. * **The mixing error -- concrete trace with `[3, 5]`, target = 3, using Template 1 conditions with Template 2 updates:** * left=0, right=1 (should be right=len=2 for Template 2, but we used right=len-1=1). * mid = 0. arr\[0]=3 >= target, so `right = mid = 0`. * left=0, right=0. Loop condition `left < right` is false. Return left=0. Correct by luck. * Now target = 5: left=0, right=1. mid=0. `arr[0]=3 < 5`, so `left = mid + 1 = 1`. left=1, right=1. Loop ends. Return 1. Correct. * But if right was initialized to `len-1` instead of `len` and target = 6: the loop exits at left=right=1, returning 1 instead of 2 (the correct insertion point). **This is the off-by-one.** * **The rule:** Template 2's right must be initialized to `len` (one past the end) because the answer might be "past all elements." Template 1's right is `len - 1` because it searches within existing elements. **Follow-up: In practice, how do you decide which template to use for a new problem in under 30 seconds during an interview?** * Ask: "Am I looking for an exact value, or a boundary?" Exact value = Template 1. First element satisfying a condition = Template 2. Last element satisfying a condition = Template 3 (or Template 2 on the complement). * If unsure, default to Template 2. It handles the most common interview scenarios and naturally converges without the `right = mid - 1` trap. **Strong Answer:** * **The most common bug:** Using `nums[left] < nums[mid]` instead of `nums[left] <= nums[mid]` when determining which half is sorted. The `=` matters for two-element subarrays where `left == mid`. Without it, a two-element subarray `[3, 1]` with mid=0 would classify the left half as unsorted, sending the search to the wrong half. * **How duplicates break O(log n):** When `nums[left] == nums[mid] == nums[right]`, you cannot determine which half is sorted. Consider `[1, 1, 1, 1, 1, 1, 1]` rotated to `[1, 1, 3, 1, 1, 1, 1]`. With mid pointing to a `1`, both halves look identical. You cannot eliminate either half with certainty. * **The only safe move with duplicates:** Shrink the search space by one element: `left += 1` (or `right -= 1`). This degrades the worst case to O(n) when all elements are equal except one. * **Why this is unavoidable:** Information-theoretically, if n-1 elements are the same and one is different, any comparison-based algorithm needs O(n) comparisons in the worst case to locate the different element. * **Interview tip:** Always ask "can the array contain duplicates?" before coding. If yes, mention the O(n) worst case explicitly. **Follow-up: If you needed to find the minimum element in a rotated sorted array with duplicates, is O(n) the best you can do?** * In the worst case (all elements equal except one), yes, O(n) is optimal. No algorithm can do better. * In the average case with random data, binary search still achieves O(log n) expected time because the duplicate collision is rare. * A practical adaptive approach: when you encounter `nums[left] == nums[mid]`, increment left by 1 and check if the next element differs. If it does, resume binary search immediately. This gives O(log n) when duplicates are sparse, degrading gracefully to O(n) only when duplicates dominate.