Divide and Conquer Strategies

From pieces to strategy

Now that we've covered Mastering Recursion, Sorting Algorithms, Understanding Hash Tables, and Graph Basics, you're ready for a pattern that shows up everywhere in medium interview problems: divide and conquer.

The idea is simple:

1. Divide a big problem into smaller versions.
2. Conquer those smaller problems, often with recursion.
3. Combine their answers into one final answer.

This lesson turns recursion from “a function calling itself” into a problem-solving strategy. You'll use it to reason about binary search, merge sort, and selection-style problems.

The divide-and-conquer template

Most divide-and-conquer algorithms fit this shape:

solve(problem):
    if problem is small enough:
        return direct answer

    left_part, right_part = split(problem)
    left_answer = solve(left_part)
    right_answer = solve(right_part)
    return combine(left_answer, right_answer)

The key question is not “can I use recursion?” You already practiced that.

The key question is:

Can I split this problem into smaller independent problems, solve them, then merge the results efficiently?

Common examples

• Binary search: split the search space, keep one side.
• Merge sort: split the array, sort both halves, merge them.
• Quickselect: partition around a pivot, recurse into only the side that matters.

Which problem description most clearly fits a divide-and-conquer strategy?

Divide by discarding

Binary search is one of the cleanest divide-and-conquer examples.

But it has a special twist: after checking the middle, we discard one half instead of solving both halves.

That is why binary search is so fast: the search space shrinks like this:

16 items → 8 → 4 → 2 → 1

The array must be sorted, connecting directly back to Sorting Algorithms.

```python
def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        print(f'checking index {mid}, value {nums[mid]}')

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

numbers = [2, 4, 7, 10, 13, 18, 21, 30]
answer = binary_search(numbers, 18)
print('found at index:', answer)
```

Binary search cuts the remaining search space in half each step. Its time complexity is _____.

Divide, solve both, combine

Merge sort is the classic full divide-and-conquer sorting algorithm.

Unlike binary search, it cannot throw away half the data. It must:

1. Split the list in half.
2. Sort the left half.
3. Sort the right half.
4. Merge the two sorted halves.

The important shift: the recursive calls make the halves sorted, and the merge step uses that sorted structure.

```python
def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])

    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

values = [8, 3, 5, 1, 9, 2]
print('original:', values)
print('sorted:', merge_sort(values))
```

True or false: In every divide-and-conquer algorithm, the combine step is always constant time.

Quickselect idea

Sometimes you do not need a fully sorted list.

Example: “Find the 3rd smallest number.”

A divide-and-conquer approach can partition around a pivot:

smaller than pivot | pivot | larger than pivot

Then recurse only into the side containing the answer.

This is the same high-level instinct as binary search: use structure to ignore work.

```python
def quickselect(nums, k):
    # k is zero-based: k = 0 means smallest
    if len(nums) == 1:
        return nums[0]

    pivot = nums[len(nums) // 2]
    lows = [x for x in nums if x < pivot]
    highs = [x for x in nums if x > pivot]
    pivots = [x for x in nums if x == pivot]

    print('pivot:', pivot, '| lows:', lows, '| pivots:', pivots, '| highs:', highs)

    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot
    else:
        new_k = k - len(lows) - len(pivots)
        return quickselect(highs, new_k)

values = [9, 1, 7, 3, 8, 2, 6]
third_smallest = quickselect(values, 2)
print('3rd smallest:', third_smallest)
```

Divide-and-conquer checklist

Try this pattern when you notice these signals:

• The input can be split into meaningful chunks.
• The chunks are smaller versions of the same problem.
• Solving one chunk does not require constantly changing the other chunk.
• There is a clear base case.
• The combine step is efficient enough.

Be careful when...

• The subproblems overlap heavily.
• Combining answers is more expensive than solving directly.
• Splitting creates lots of copied arrays unnecessarily.

That first warning is a gentle preview: in the next lesson, Dynamic Programming Essentials, we'll look at what to do when subproblems repeat.

Practice plan

Because this crash course revisits problems every 2 days, don't just “understand” divide and conquer once. Put it into your review loop.

Today

• Re-code binary search without looking.
• Trace merge sort on [4, 1, 3, 2] by hand.
• Explain what the combine step does in one sentence.

In 2 days

• Revisit binary search.
• Revisit merge sort's merge function.
• Try one problem where you find a minimum, maximum, or kth element using splitting.

Your mental shortcut

Ask:

“Can I cut the problem down, solve smaller versions, and avoid unnecessary work?”