Divide and conquer

Three steps: divide, conquer, combine

Divide and conquer is a way to design recursive algorithms. Divide: split the input into smaller parts, usually two halves. Conquer: solve each part with a recursive call (tiny parts are base cases). Combine: build the full answer from the answers of the parts. Recursion from Topic 1 shrinks the problem by one each time; divide and conquer shrinks it by half, which is why it is so much faster and so much shallower.

Fast power: x^n in O(log n)

The simple power from Topic 1 makes n multiplications. But x^n = (x^(n/2))² when n is even, and x × x^(n−1) when n is odd. Compute the half power ONCE, store it, and square it. Each step halves n, so there are about log₂ n steps, each with one or two multiplications. This idea is called exponentiation by squaring.

def fast_pow(x, n):
    if n == 0:
        return 1
    half = fast_pow(x, n // 2)   # one recursive call, stored
    if n % 2 == 0:
        return half * half
    return half * half * x

print(fast_pow(2, 10))   # Output: 1024
print(fast_pow(3, 5))    # Output: 243

In contests and in cryptography, powers are huge, so you take the remainder modulo m at every multiplication: (a × b) mod m = ((a mod m) × (b mod m)) mod m. The numbers then never grow beyond m², and x^n mod m costs O(log n) multiplications. Python's built-in pow(x, n, m) uses the same idea.

Binary search, recursively

In a sorted list, compare the target with the middle item. If they are equal, you are done. If the target is smaller, it can only be in the left half; otherwise the right half. That is divide and conquer with only ONE half to solve and nothing to combine. The recurrence is T(n) = T(n/2) + O(1), which is O(log n) time and O(log n) stack space. Module 6 writes it as a loop with O(1) space and adds the tricky variants.

def bsearch(nums, target, lo=0, hi=None):
    if hi is None:
        hi = len(nums) - 1
    if lo > hi:                      # empty range: not found
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return bsearch(nums, target, mid + 1, hi)
    return bsearch(nums, target, lo, mid - 1)

print(bsearch([2, 5, 8, 12, 16], 12))   # Output: 3
print(bsearch([2, 5, 8, 12, 16], 7))    # Output: -1

Merging two sorted halves

Merge sort is divide and conquer with a real combine step. Split the list in half, sort each half recursively, then merge: two fingers walk the two sorted halves, and the smaller of the two current items goes to the output each time. Merging is O(n), the recursion is log₂ n levels deep, and every level merges n items in total, so merge sort is O(n log n), the recurrence T(n) = 2T(n/2) + n you met in Module 1. Module 6 builds the full sort.

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

print(merge([1, 4, 9], [2, 3, 10]))   # Output: [1, 2, 3, 4, 9, 10]

Counting inversions: an idea to remember

An inversion is a pair of positions i < j where nums[i] > nums[j]; it measures how unsorted a list is. Checking every pair is O(n²). During a merge, whenever an item from the RIGHT half is placed before the remaining items of the left half, it forms an inversion with every one of them, so you add len(left) − i in one step. Counting during merge sort gives all inversions in O(n log n). You will code it in Module 6.

Common mistakes

• Slicing halves (nums[:mid], nums[mid:]) inside binary search: each slice copies, so the search becomes O(n). Fix: pass lo and hi indexes.
• Calling the same half twice in fast power. Fix: store half = fast_pow(x, n // 2) once.
• Forgetting the base case for an empty or one-item range, so the recursion never ends. Fix: handle lo > hi (empty) and lo == hi (one item) first.
• Computing mid so the range does not shrink, for example recursing on (lo, mid) when mid can equal hi. Fix: use mid − 1 and mid + 1 after checking mid, or test a two-item range by hand.
• Not taking the remainder at every step in modular power, so numbers grow huge and slow. Fix: apply % m after every multiplication.