Lesson 6 of 10 · 9 min

Sorting and binary search

Know what Python's sort guarantees, and learn to binary search the answer rather than the array.

The O(n log n) floor

Any algorithm that sorts purely by comparing elements must distinguish n! possible orderings. A decision tree doing that needs depth at least log₂(n!), which works out to roughly n log n. No comparison sort can do better.

Counting sort and radix sort beat it precisely because they do not rely only on comparisons — they exploit the structure of the keys. The catch is that counting sort's cost includes the key range, so it is only useful when that range is small.

Stability, and why it is useful

A stable sort preserves the relative order of equal elements. Python's Timsort is stable.

That lets you sort by several keys: sort by the least significant key first, then by the more significant one, and the earlier ordering survives within ties. Or pass a tuple key and get the same effect in one pass — `key=lambda x: (-count[x], x)` sorts by descending frequency then ascending value.

Binary search, written so it always terminates

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1      # must be mid + 1, or lo can stick
        else:
            hi = mid          # mid may be the answer, so keep it
    return lo                 # first index where a[i] >= target

Note: Every branch must strictly shrink the interval. `lo = mid` is the classic infinite loop.

Binary search on the answer

The deeper idea is that binary search does not need a sorted array — it needs a monotone predicate. If 'can we do it with capacity X?' is false below some threshold and true above it, you can binary search X.

That covers a whole family of problems phrased as 'minimise the maximum' or 'maximise the minimum': shipping capacity within D days, the smallest divisor under a threshold, splitting an array into k parts.

Searching the answer space

def min_capacity(weights, days):
    def feasible(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used += 1
                load = 0
            load += w
        return used <= days

    lo, hi = max(weights), sum(weights)   # lower bound must fit the largest item
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Worth remembering

Comparison sorting cannot beat O(n log n) — that is an information-theoretic bound.
Python's sort is stable, which lets you build compound orderings.
Binary search works on any monotone predicate, not only on sorted arrays.

Test it now

Binary-search-on-the-answer is a favourite medium and hard topic.

Medium DSA quiz →All levels