LeetCode Patterns Flashcards: Binary Search, Search Space, Templates, Edge Cases

Binary search eliminates half the search space at each step by comparing the target with the middle element and deciding which half to continue searching. It applies whenever the search space has a monotonic property where all elements on one side satisfy a condition and all on the other do not. The input does not have to be a sorted array. Binary search works on any decision function that transitions from false to true or true to false at some boundary point.

A rotated sorted array has two sorted halves. At each step, calculate the midpoint and determine which half is sorted by comparing the mid value with the leftmost value. If the left half is sorted and the target falls within its range, search left; otherwise search right. If the right half is sorted and the target falls within its range, search right; otherwise search left. The key insight is that at least one half is always properly sorted after rotation, and you can check if the target falls in the sorted half to make the correct elimination decision. This maintains O of log n time.

Instead of searching within the input array, binary search on the answer space searches for the optimal value in a range of possible answers. Define the minimum and maximum possible answers, then binary search for the boundary where a feasibility check function transitions from possible to impossible. For example, "minimum capacity to ship within d days" has answers ranging from the maximum package weight to the total weight sum. For each candidate capacity at the midpoint, greedily check if shipping within d days is feasible. If feasible, try a smaller capacity; if not, try a larger one.

Standard binary search stops at any occurrence. To find the first occurrence, when you find the target at mid, do not return immediately. Instead, record mid as a candidate and continue searching the left half by setting right to mid minus one. To find the last occurrence, record mid and continue searching the right half by setting left to mid plus one. After the loop ends, return the recorded candidate. This ensures you find the boundary occurrence rather than an arbitrary one.

Off-by-one errors in binary search come from three sources: the loop condition, the mid calculation, and the pointer updates. Use "left less than or equal to right" when searching for an exact target, and "left less than right" when converging to a boundary. Calculate mid as left plus right minus left divided by two to avoid integer overflow. When eliminating the left half, set left to mid plus one. When eliminating the right half, set right to mid minus one for exact search or right to mid for boundary search.

A peak element is greater than its neighbors. Compare the mid element with mid plus one. If mid is greater, a peak exists on the left side including mid, so set right to mid. If mid plus one is greater, a peak exists on the right side, so set left to mid plus one. This works because if you are going uphill, there must be a peak ahead or at the end. The loop converges when left equals right, pointing to a peak. This finds any peak, not necessarily the global maximum. ---