2.2.2 - Divide and conquer

Split a problem and combine its answers

Divide and conquer splits a problem into smaller subproblems, solves them and uses their results to obtain the original answer. The smaller instances often have the same structure, so recursion expresses the repeated rule. A base case solves an instance directly.

To find the highest reading in a non-empty list, split the list into two non-empty halves. Find each half's highest reading, then compare those two results. A one-element list returns its only value. For [8,3,11,5], solve [8,3] and [11,5]; these return 8 and 11; combining returns 11. Inside each two-item half, the one-item base cases return their readings before comparison.

The answer has not been guessed from the first half. Both maxima are required because the highest value might be anywhere. Other problems use different combination rules: two partial counts are added; two sorted halves are merged. A split alone is insufficient if the partial results cannot be combined correctly.

For a sum of qualifying values, a one-item subproblem contributes that value if it qualifies, otherwise 0; an empty subproblem contributes 0. Add the partial sums from both halves. For values [4,-2,7,3] strictly below 4, the contributions are 0,-2,0,3, so the sum is 1. This is a sum of values, whereas a qualifying count adds 1 for each qualifying item.

Decomposition is the wider practice of separating responsibilities. “Read a file, check its records, print a report” decomposes work into different operations. Divide and conquer here repeats the same maximum-finding problem on smaller inputs and combines its answers. Binary search also uses division to narrow an ordered search, but discards the half that cannot contain the target rather than solving both halves.

Implement a progressing recursive split

A recursive split must reduce the problem and cover the input exactly once. Use zero-based half-open index ranges, [start,stop), so a range contains stop-start elements. The whole list has range [0,len(values)); an empty range has start == stop.

The function below counts readings strictly above a limit. Inputs are a finite list of numbers, a numeric limit and valid bounds 0 <= start <= stop <= len(values). It does not modify the list. Read the source first, then use the ungraded sandbox to test your prediction.

def count_above(values, limit, start, stop):
    size = stop - start
    if size == 0:
        return 0
    if size == 1:
        if values[start] > limit:
            return 1
        return 0
    middle = start + size // 2
    left = count_above(values, limit, start, middle)
    right = count_above(values, limit, middle, stop)
    return left + right

For a size of at least two, start < middle < stop, so both recursive ranges are smaller. The ranges share a boundary but no index. values[middle] belongs to the right range. Empty and single-item ranges avoid attempting another split. Invalid bounds or nonnumeric entries are outside this function's contract; an interface must check them if it accepts untrusted input.

For [4,9,2,7,9] with limit 7, the outer range [0,5) splits at 2. [0,2) gives 1 from [4,9]; [2,5) gives 1 from [2,7,9]; the final sum is 2. Reading 7 is excluded because the comparison is strictly greater than 7. Replacing middle with start would reproduce the original right range and prevent progress.