Summary - Divide and conquer

Solve a problem by dividing it in a mini task.

Summary - Divide and conquer

Divide and conquer solves problems by dividing, conquering recursively and combining. Merge sort, quick sort and binary search use it.

In this mini task you will count using divide and conquer; combine all steps.

The approach also runs well on parallel hardware; subproblems are independent.

Exercise Divide and count

Write dc_count(arr, target). Split in half, count target recursively in each half, add. Print 3 with print(dc_count([1, 2, 1, 3, 1], 1)).

Show example solution

def dc_count(arr, target):
    # Divide and count
    if len(arr) == 0:
        return 0
    if len(arr) == 1:
        return 1 if arr[0] == target else 0
    mid = len(arr) // 2
    return dc_count(arr[:mid], target) + dc_count(arr[mid:], target)
print(dc_count([1, 2, 1, 3, 1], 1))

Test yourself

Summary - Divide and conquer: match the terms

divide

Split
conquer

Solve
combine

Merge
base case

Stop

Find mid

mid = len(arr) ____ 2

Show answer

mid = len(arr) // 2

Where is divide and conquer used?
- Linear search
- Merge sort, quick sort
- Bubble sort
- Heap only
Show answer

Merge sort, quick sort — Merge sort, quick sort.

Next lesson: What is backtracking?

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies