Sorting and binary search

Why it matters

Sorted data makes many questions easy: duplicates become neighbors, pairs can be found with two pointers, intervals merge in one pass and lookups take O(log n). Binary search is how you exploit order, and its general form, finding the first point where a monotone condition becomes true, solves optimization problems that do not look like searching at all. Both are classic places for interviewers to check off-by-one discipline and whether you can state an invariant.

Core ideas

Sorting algorithms. Merge sort is Θ(n log n) in the worst case, stable, and uses O(n) extra space. Quicksort is O(n log n) expected with random pivots but O(n²) in the worst case, and in place apart from its recursion. Heap sort is O(n log n) worst case and in place but not stable. Insertion sort is O(n²) yet fast on tiny or nearly sorted inputs, which is why hybrid library sorts use it for small runs. Library sorts are hybrids; know whether yours is stable (Python, Java object sorts and JavaScript are; C++ std::sort is not).

The lower bound. A comparison sort must distinguish all n! input orders, and a binary decision tree with n! leaves has height at least log₂(n!) = Θ(n log n). Counting sort (O(n + k) for keys in a range of size k) and radix sort escape the bound because they use key values, not just comparisons.

Pattern: Sorting as preprocessing. If the answer does not depend on input order, sort first and pay O(n log n): 3Sum, Merge Intervals, meeting-room overlaps and many greedy problems start this way. Ask whether reordering is allowed; if original indices matter, sort (value, index) pairs.

Pattern: Binary search on a sorted space. Use an explicit invariant:

lo, hi = 0, len(a)        # invariant: the answer index lies in [lo, hi]
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < target:    # a[mid] and everything left of it are too small
        lo = mid + 1
    else:                  # mid itself may be the answer
        hi = mid
return lo                  # first index with a[i] >= target, or len(a)

This is lower_bound; changing < to <= gives upper_bound, the first index with a[i] > target, and the count of target values is their difference. Every iteration shrinks the interval, so the loop terminates, and when it ends lo is the boundary. In fixed-width languages compute the midpoint as lo + (hi - lo) / 2 to avoid overflow.

Pattern: Binary search on the answer. Binary search needs a predicate that is false and then true across an ordered search space, not a sorted array. In Koko Eating Bananas, "all piles can be finished within h hours at speed s" is monotone in s, so you search for the smallest feasible s between 1 and the largest pile, checking each candidate in O(n): O(n log max) in total. Write the predicate first, argue monotonicity, then choose bounds that surely contain the answer.

Implicit search spaces. In a rotated sorted array with distinct values, one half around mid is always sorted; check whether the target lies inside that half and discard the other. For a peak, comparing a[mid] with a[mid + 1] tells you which side must contain one. A row-major sorted matrix is a sorted array of length rows × cols.

Common misconceptions

• "Binary search needs a sorted array." It needs a monotone predicate over an ordered space; a sorted array is one example.
• "Quicksort is O(n log n)." Only in expectation with random pivots; a simple deterministic pivot rule (first, last or middle element) has inputs that force O(n²).
• "Any comparator works." A comparator must define a consistent ordering; inconsistent ones give wrong output, runtime errors or, in C++, undefined behavior.
• "Stability is irrelevant." It matters whenever you sort by one key after another or need ties to keep input order.
• "lo <= hi or lo < hi is a matter of taste." Each form needs matching updates and a matching meaning for the final index; mixing them causes infinite loops or skipped answers.

How to approach it

Ask whether sorting is allowed and add its cost to the total. For binary search, write the invariant as a comment before the loop and say what lo means at the end. Test an empty array, one element, all-equal elements and targets below and above the range. Interviewers probe boundary handling, the monotonicity argument in search-on-answer problems, and, at deeper levels, quicksort's worst case, stability and the lower bound.