Sorting, Searching, and Intervals

What can you stop reconsidering?

Suppose a sorted array is [2, 2, 4, 7, 7] and the target is 5. There is no matching element, yet there is a precise answer worth finding: index 3, the place where 5 could be inserted without breaking the order.

Viewed as comparisons with the target, the array has this shape:

value >= 5:  false  false  false  true  true
index:          0      1      2      3     4
                                  ^
                              first true

That change from false to true is the useful object. A correct search does not merely visit promising midpoints. Each comparison proves that a whole region can no longer contain the boundary.

Sorting, interval scans, sweep lines, and selection algorithms make the same kind of bargain. They spend work to create an order, then use that order to make decisions irreversible. The decisive question is therefore not “Which template fits?” It is “After this step, what will I never need to reconsider?”

A search is its invariant

For a lower bound, the job is to return the first index whose value is at least the target. The answer may be len(nums) when every value is smaller.

def lower_bound(nums, target):
    lo = 0
    hi = len(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= target:
            hi = mid
        else:
            lo = mid + 1

    return lo

Before every iteration:

• every index before lo is known to contain a value smaller than target;
• every in-array index at or after hi is known to contain a value at least target;
• the first qualifying index remains somewhere in [lo, hi].

If nums[mid] >= target, mid may be the first true position, so the search keeps it by setting hi = mid. Otherwise mid is disproved and joins the false region through lo = mid + 1. When the two boundaries meet, the unknown region is empty.

Change the predicate to nums[mid] > target and the same loop finds the upper bound. The pair composes into a range without two bespoke searches:

first = lower_bound(nums, target)
after = upper_bound(nums, target)
count = after - first

If the caller needs a found-or-missing answer, check first < len(nums) and nums[first] == target. A bound returns a position, not a promise that the target exists.

Closed binary search is also valid, but it has a different contract. With lo = 0, hi = n - 1, and while lo <= hi, the unknown region is inclusive. After proving nums[mid] > target, the update must be hi = mid - 1 because mid has already been eliminated. Most binary-search bugs are not failures to remember syntax. They are collisions between two different meanings of the endpoints.

A rotated sorted array makes that discipline visible. The whole range is not ordered, but with distinct values at least one side of a midpoint is. The algorithm may discard that side only after determining whether its ordered range can contain the target. Duplicates weaken the observation: when the left, middle, and right values are equal, neither side may reveal useful order, and worst-case progress can become linear.

Search an answer you never sorted

Now consider a nonempty sequence of positive package weights that must be shipped in order within at least one day. The packages are not the search space. Capacity is.

For any proposed capacity, a linear scan can answer a yes-or-no question: does that capacity finish within the deadline? If capacity C works, every larger capacity works as well. The possible answers therefore have the same false-then-true shape as the sorted-array predicate.

def minimum_ship_capacity(weights, days):
    lo = max(weights)
    hi = sum(weights)

    def feasible(capacity):
        used_days = 1
        load = 0

        for weight in weights:
            if load + weight > capacity:
                used_days += 1
                load = 0
            load += weight

        return used_days <= days

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

The initial bounds carry part of the proof. A capacity below the heaviest package is impossible. The sum of all weights is sufficient for one day. The greedy feasibility scan fills a day until the next package does not fit; starting a new day earlier could not reduce the number of days because order is fixed.

The running time is O(n log R), where R is the inclusive capacity range. That expression is meaningful only after monotonicity has been established. Before searching a speed, distance, load, time, or threshold, try to construct a counterexample in which a larger answer becomes infeasible again. If one exists, binary search on the answer has no boundary to find.

Sort until the future cannot revise the past

Sorting earns its cost when it turns a global problem into a finalizing scan. Interval merging is the cleanest example, provided the endpoint convention is settled first.

Closed intervals [start, end] include both endpoints, so [1, 2] overlaps [2, 3]. Half-open intervals [start, end) do not overlap at that boundary. Neither convention is universally correct. Calendar bookings, integer ranges, and occupied byte offsets may require different contracts.

For closed intervals, sort by start and then end:

def merge_closed(intervals):
    merged = []

    for start, end in sorted(intervals):
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)

    return merged

At every step, merged exactly covers the intervals already seen, and its last range is the only one the next interval could extend. Nondecreasing start times make all earlier ranges unreachable by the future. For half-open ranges that should remain separate when they merely touch, the new-range test becomes start >= merged[-1][1].

The order must fit the decision. Sorting by start supports merging because it makes old ranges final. Sorting by end supports a different question: choosing the largest number of compatible intervals. Selecting the compatible interval with the earliest finish leaves at least as much remaining time as selecting any later-finishing alternative; exchanging the first choice cannot make the rest of an optimal schedule worse.

A custom comparator makes an even stronger claim: every pairwise decision must participate in one consistent global order. For the “largest concatenated number” problem, ordinary numeric order fails. The strings "3" and "30" must be compared as "330" versus "303", so "3" comes first.

This is algorithmic logic, not sorting syntax. The comparator must be transitive, must handle equality coherently, and must not depend on state that changes during the sort. In fixed-width integer languages, a subtraction comparator such as a.start - b.start can overflow; explicit comparison or a library comparison helper is safer.

Equal events are a policy decision

A sweep line turns every interval into changes on an ordered axis. Between two adjacent event coordinates, the active state is constant. At an event coordinate, however, correctness depends on what simultaneous changes mean.

For positive-duration half-open meetings [start, end), a meeting ending at 10:00 releases its room before one starting at 10:00 claims a room:

def maximum_rooms(meetings):
    events = []
    for start, end in meetings:
        events.append((start, 1))
        events.append((end, -1))

    # -1 sorts before +1 when times are equal.
    events.sort()

    active = 0
    maximum = 0
    for _, change in events:
        active += change
        maximum = max(maximum, active)

    return maximum

Here active means rooms occupied after applying each event in the declared tie order. If endpoints were inclusive, a start and an end at the same time would overlap, so starts would need to be processed first. More complicated events may need an explicit priority such as (coordinate, event_kind, id). The tie-break is the policy in executable form.

Merging and sweeping answer different questions. Merge when the output is the union of covered ranges or the gaps between them. Sweep when the output depends on changing active state: maximum overlap, concurrent resource usage, or another aggregate over an axis. The shared input noun “interval” does not choose the algorithm.

Selection stops when one rank is settled

Full sorting determines every rank. If the result needs only the kth item, quickselect can stop as soon as that rank becomes final.

target = k - 1            # kth smallest, zero-based
lo = 0
hi = n - 1

while lo <= hi:
    pivot = partition(values, lo, hi)

    if pivot == target:
        return values[pivot]
    if target < pivot:
        hi = pivot - 1
    else:
        lo = pivot + 1

After a correct partition, the pivot is in its final rank position. Nothing on the other side can be the target, so quickselect abandons that entire region. Randomized pivots give expected O(n) time, while consistently poor pivots can degrade to O(n²). A three-way partition is often clearer when many values equal the pivot.

The output contract decides whether selection is enough. For kth largest, the ascending zero-based target is n - k. For an unordered top-k collection, partitioning may suffice. For top k in sorted order, the selected region still needs ordering. For a stream, quickselect cannot retain a boundary over future arrivals; a fixed-size heap is the better fit.

Spend only the order the result uses

These algorithms differ in how much order they purchase:

• binary search consumes an existing monotonic order and resolves half of the remaining uncertainty at each step;
• sort-and-scan pays for complete order once so earlier decisions become final;
• a sweep orders changes, then maintains only the active state between them;
• quickselect creates just enough partition order to settle one rank;
• a heap continually repairs enough order to expose one changing extreme;
• a balanced search tree preserves ordered lookup while updates continue.

Asymptotic cost matters, but it is not the only budget. Mutation, stable output, worst-case guarantees, comparator complexity, and the ease of explaining an equality case all belong in the choice. An O(n log n) sort is often the stronger engineering answer when it makes the proof and output contract plain.

Practice by moving the boundary

Implement lower and upper bound once, then use them to return the first and last occurrence of a target. Test an empty array, a missing value between two elements, duplicates at both ends, and a target larger than every value.

Change the shipping problem from minimum feasible capacity to maximum feasible spacing. Before changing the loop, write the new truth pattern across the answer domain and decide whether you are looking for the last true value or the first false one.

Merge the same intervals twice: first as closed ranges, then as half-open ranges. Use [1, 2] and [2, 3] so one inequality must change the result. Then compute maximum overlap from events and explain the equal-time policy without referring to the code.

Find kth largest by sorting, by a size-k heap, and by quickselect. For each version, change the requested output to a descending top-k list. Notice which algorithm has already paid for that order and which still owes it.

The durable habit is to name the settled region before optimizing the loop. Say what lies beyond reconsideration, why equality belongs on one side, and what new contract would move the boundary. Once those statements are exact, the code usually becomes shorter—and its failures much easier to find.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 33: Correctness Before Cleverness
• Chapter 42: Heaps and Ordered Structures
• Chapter 44: Trees and Tries