Sorting & Searching

Sorting and binary search are the two most fundamental algorithmic tools. The core insight for sorting: comparison-based sorts cannot beat O(n log n) — mergesort, quicksort, and heapsort all achieve this. Binary search's power extends far beyond finding a target in a sorted array: the 'binary search on answer' template solves any problem where the answer space is monotonic. Internalize the partition algorithm (for quicksort and quickselect), the merge algorithm, and both the classic and boundary-finding binary search templates. Understanding Binary Search Binary search halves the search space in each step, achieving O(log n) time. It works on sorted data and is one of the most powerful techniques in interviews. The template: Define search space: left = 0, right = n-1 While left <= right: compute mid = left (right left) / 2 If target found at mid: return If target < arr[mid]: search left half (right = mid 1) If target arr[mid]: search right half (left = mid 1) Variations: Find leftmost occurrence: when found, keep searching left (right = mid 1) Find rightmost occurrence: when found, keep searching right (left = mid 1) Search in rotated array: determine which half is sorted, then decide direction Search on answer: binary search on the result space (e.g., "minimum capacity to ship") Common mistakes: Integer overflow: use mid = left (right left) / 2 instead of (left right) / 2 Off-by-one errors in left/right boundaries Infinite loops when not narrowing the search space Sorting & Searching Know the trade-offs between sorting algorithms and when to use each. Algorithm Comparison Time (Avg) Space O(n log n) O(log n) O(n log n) O(n) O(n log n) O(1) O(n+k) O(k) QuickSort Binary Search Variants Key Problems #912 Sort an Array, #75 Sort Colors (Dutch National Flag) #33 Search in Rotated Sorted Array, #34 First and Last Position Interview Tip "I default to QuickSort for in-place sorting and MergeSort when stability matters. For interviews, knowing QuickSelect for kth element (O(n) average) is a strong signal." Java Implementation: