Binary Search

What you'll learn

• The Golden Rule

  When can you use binary search? Binary search applies whenever you have a sorted or monotonic search space where you can eliminate half the candidates at each step. This is not limited to sorted arrays. Binary search works on any space w…

• Why Binary Search is O(log n)

  Each step eliminates exactly half the remaining search space. Starting with n elements: We stop when the space reduces to 1 element: n / 2^k = 1, so k = log2(n). For n = 1,000,000, linear search may need 1,000,000 comparisons. Binary sea…

• Three Core Templates

• Template 1: Standard Binary Search (Find Exact Target)

  Key details: - Loop condition: lo Why continue searching left after finding a match? Because there might be an earlier occurrence. We record the current position as a candidate and narrow the search to the left half. ASCII Trace — findin…

• Template 3: Right Boundary (Find Last Occurrence / Upper Bound)

  The logic mirrors Template 2 but searches rightward after finding a match. ---

• Common Off-by-One Pitfalls

• Inclusive vs Exclusive Bounds

  | Style | Init | Loop Condition | Shrink | |-------|------|---------------|--------| | Both inclusive | lo=0, hi=n-1 | lo The count of the target element = last - first + 1. ---

• Pattern 3: Search in Rotated Sorted Array

  A sorted array rotated at some pivot looks like two sorted segments: Key Insight: At any midpoint, at least one half is always sorted. We can determine which half is sorted and whether our target falls within that sorted half. How to ide…

• Pattern 4: Find Peak Element

  A peak element is greater than its neighbors. The array may have multiple peaks; find any one. Key Insight: If the middle element is less than its right neighbor, a peak must exist to the right (the values are still increasing). If it is…

• Pattern 5: Search in 2D Matrix

• Variant A: Rows and columns individually sorted, first element of each row > last element of previous row

  Treat the 2D matrix as a flattened 1D sorted array. Time: O(log(m n)) | Space: O(1)

• Variant B: Each row sorted, each column sorted (but no global ordering)

  Use a staircase search starting from top-right or bottom-left corner. Time: O(m + n) | Space: O(1) ---

• Pattern 6: Binary Search on Answer Space

  This is one of the most powerful applications of binary search. Instead of searching through data, we search through the space of possible answers. Pattern recognition: Problems that ask you to "minimize the maximum" or "maximize the min…

• Example A: Minimum Capacity to Ship Packages in D Days

  Given package weights and D days, find the minimum ship capacity to ship all packages within D days (packages must stay in order).

• Example B: Split Array Largest Sum

  Split an array into k subarrays to minimize the largest subarray sum. The answer space is [max(array), sum(array)]. The feasibility check asks: "Can we split the array into at most k parts such that no part exceeds the candidate sum?"

• Example C: Koko Eating Bananas

  Koko eats bananas at speed k (bananas per hour). Given piles and h hours, find minimum k. Answer space: [1, max(piles)]. Feasibility: sum(ceil(pile/k) for each pile) right, the minimum is in the right half. If mid ---

• Pattern 8: Median of Two Sorted Arrays

  Given two sorted arrays of size m and n, find the median in O(log(min(m,n))) time. Core Idea: We need to partition both arrays such that: - All elements in the left partition B[j]: move i left. If B[j-1] > A[i]: move i right. Time: O(log…

• Complexity Summary

  | Pattern | Time | Space | |---------|------|-------| | Standard search | O(log n) | O(1) | | Left/Right boundary | O(log n) | O(1) | | Rotated array search | O(log n) | O(1) | | Find peak | O(log n) | O(1) | | 2D matrix (sorted) | O(log…

• Decision Framework Summary

  Quick checks before applying binary search: 1. Is the input sorted? (or can it be treated as sorted?) 2. Is there a monotonic predicate on the answer space? 3. Can you define "go left" and "go right" conditions clearly? If all three are…

• Common Mistakes to Avoid

  1. Wrong midpoint formula: Always use lo + (hi - lo) // 2 to prevent overflow 2. Wrong loop termination: lo <= hi for standard search, lo < hi for boundary search 3. Forgetting edge cases: Empty array, single element, all elements equal…