Core Concepts

• 1Classic binary search — why it works: binary search exploits a sorted array's guarantee that if arr[mid] < target, all elements to the left of mid are also less than target. So we can discard the entire left half in one step. Each step halves the search space: n → n/2 → n/4 → ... → 1, giving O(log n) iterations. The loop invariant is: 'the answer (if it exists) is always in [left, right]'. Three exit conditions determine the template: (1) find exact value, (2) find first position where condition is true (bisect_left), (3) find last position where condition is true (bisect_right). Getting the boundary conditions right — whether to use left <= right or left < right, and whether to set mid = (l+r)//2 or mid = (l+r+1)//2 — is the main source of bugs.
• 2Template 1 — exact match (while left <= right): use left=0, right=n-1, mid=(left+right)//2. If arr[mid]==target return mid. If arr[mid]<target set left=mid+1. If arr[mid]>target set right=mid-1. Loop exits when left>right meaning element not found. This is the 'closed interval' template — both left and right are inclusive. The update rules (left=mid+1, right=mid-1) ensure you never revisit mid, preventing infinite loops. Return -1 if not found. Time O(log n), Space O(1).
• 3Template 2 — first/last occurrence (bisect_left / bisect_right): to find the FIRST position where arr[pos] >= target (lower bound), use left=0, right=n. Loop while left<right. Set mid=(left+right)//2. If arr[mid]<target: left=mid+1 (mid is too small, left side is dead). Else: right=mid (mid might be the answer, keep it). When loop exits, left==right is the answer index. For LAST occurrence (upper bound, first pos where arr[pos]>target), change the condition to arr[mid]<=target: left=mid+1. These two templates form the foundation of Python's bisect_left and bisect_right. Crucial: using right=n (not n-1) allows the answer to be 'insert at the end'.
• 4Search on answer space — the key paradigm shift: instead of searching for a value in an array, binary search on the ANSWER ITSELF. The question becomes: 'can I achieve result X?' where the feasibility function is monotonic (once X is achievable, all larger X are also achievable, or vice versa). Template: left=min_possible_answer, right=max_possible_answer. While left<right: mid=(left+right)//2; if feasible(mid): right=mid; else: left=mid+1. Return left. This pattern solves: Koko eating bananas (can she eat all bananas in H hours at speed k?), minimum days to make bouquets, capacity to ship packages within D days, split array largest sum. The feasibility check is usually O(n), making total complexity O(n log(answer_range)).
• 5Rotated sorted array — the insight: after rotation, at least ONE half of the array is still sorted. At index mid, compare with left (or right) endpoint to determine which half is sorted. If arr[left] <= arr[mid], the left half [left..mid] is sorted. If target is in [arr[left], arr[mid]), search left; otherwise search right. If arr[mid] < arr[left], the right half [mid..right] is sorted. If target is in (arr[mid], arr[right]], search right; otherwise search left. The condition arr[left] <= arr[mid] handles the case where the rotation point is in the right half. For duplicates (LC 81), if arr[left]==arr[mid]==arr[right] you can't determine which side is sorted — fall back to left++, right-- (degrades to O(n) worst case).
• 6Search in 2D matrix: LC 74 (strictly sorted matrix where each row's last element < next row's first) can be treated as a 1D sorted array of n*m elements. Map 1D index i → (i//cols, i%cols). Standard binary search gives O(log(n*m)). LC 240 (each row and column sorted but rows not connected) requires a different approach: start at top-right corner (or bottom-left). If current > target: move left (current column is too big). If current < target: move down (current row is too small). This staircase search is O(n+m) — not O(log(n*m)), which is actually impossible to achieve in general for LC 240.
• 7Find peak element — binary search on non-comparison: a peak is defined as an element greater than its neighbors. The key insight: if arr[mid] < arr[mid+1], then the RIGHT half must contain a peak (arr[mid+1] is greater than arr[mid] and if you keep going right and never find a bigger neighbor, you'll hit the right boundary which counts as a peak). So set left=mid+1. If arr[mid] > arr[mid+1], set right=mid (mid itself might be the peak). The loop with left<right converges to a peak. No comparison to a target value — just a local slope direction. This shows binary search applies to ANY property that can tell you 'go left' or 'go right', not just comparisons to a fixed value.
• 8Median of two sorted arrays — O(log(min(m,n))): the key insight is to binary search on the partition of the SMALLER array. If we put the first k elements of array A in the left partition and the first (total_left - k) elements of array B, we have a valid median partition when: A[k-1] <= B[total_left-k] AND B[total_left-k-1] <= A[k]. Binary search k in [0, len(A)]. This is the hardest binary search problem in interviews — it requires understanding that finding the median is equivalent to finding the right partition, and that binary searching on the partition index is valid because the arrays are sorted. O(log(min(m,n))) time. Only needed at senior/staff level.
• 9Common bugs and how to avoid them: (1) Infinite loop with left=mid — when target is right=mid, and left=mid would create a cycle. Fix: use mid=(left+right+1)//2 (round up) when right=mid is not chosen. (2) Integer overflow — (left+right) can overflow in Java/C++. Use left + (right-left)//2 instead. Python has arbitrary precision integers so no overflow. (3) Off-by-one in bounds — always test with arrays of size 1, 2, and the target at the extreme ends. (4) Wrong feasibility direction — make sure feasible(mid)=True leads to a smaller search space, not an infinite loop. Sketch the monotonic function before coding.

Key Patterns & Templates