DSA sheet · Recursion · Pattern 3: divide and conquer

Divide & Conquer (Binary Search)

This video starts the third recursion pattern: divide and conquer. The teacher calls it a kind of non-linear recursion with one big difference: the smaller problems never overlap, so no call ever repeats work and no DP (dynamic programming) is needed. She explains it with the best-known example, binary search: first the slow linear search, then the usual binary search with a while loop, and finally the same algorithm rewritten as a recursive function.

Why it matters: binary search appears everywhere. And the "turn the loop into recursion" steps you learn here (loop condition → base case, pointer updates → new arguments) work for many other problems. Merge sort and Median of Two Sorted Arrays come next in the same pattern.

This is a concept video, so the order is:
① what the pattern is → ② how to recognise it → ③ the intuition → ④ the example problem, worked fully (question, constraints, logic, steps, code, line by line, recursion tree + call stack, complexity) → ⑤ a pattern template in Python → ⑥ remember

• Part 0 · Recursion from scratch (what you need for this page)
• Part A · The divide and conquer pattern (what, how to spot it, why no overlap)
• Part B · Example: search a sorted array: linear search → iterative binary search
• Part C · Binary search as divide and conquer recursion
• Part D · Pattern template
• Part E · Revision page

Part 0 · Recursion from scratch

1. A function that calls itself

Recursion means a function solves a problem by calling itself on a smaller piece of the same problem. In binary search, "find 5 in positions 0 to 5" becomes "find 5 in positions 3 to 5". It's the same question on a smaller range, so the same function can answer it.

2. The base case: where it must stop

The base case is a situation simple enough to answer directly, without another call. Without it, the function would call itself forever. Python stops this after about 1000 nested calls with a RecursionError (you can raise the limit with sys.setrecursionlimit, but a missing base case is a bug, not a limit problem). In binary search there are two ways to stop: the range has become empty (not found), or the middle element is the target (found).

3. The recursive case: make the problem smaller

The recursive case calls the function again on a smaller input. Each call must move closer to the base case. In binary search, the range at least halves every time, so it must eventually become empty or hit the target.

4. Trust the smaller call ("leap of faith")

When the code says "search the right half", just trust that the call returns the correct index (or −1) for that half. Don't trace it in your head. You only need to make sure that (a) the base cases are right and (b) you pick the correct half. That trust is called the leap of faith.

5. The call stack: push on call, pop on return

Python keeps a call stack: a pile of calls that have started but not finished. A new call is pushed on top and the caller waits. When a call returns, it is popped, and its answer goes to the call below it. The tallest the pile gets is the depth, and that is the extra memory the recursion uses.

6. Work on the way down vs on the way back up

Some recursions do their real work after the smaller call returns (on the way back up, e.g. adding up results). Binary search does all its work on the way down (computing mid, comparing, choosing a half). On the way back up, each call just passes the answer it received to its caller, unchanged.

Part A · The divide and conquer pattern

1What the pattern is

Divide and conquer solves a problem in three moves:

1. Divide: split the input into smaller parts, usually two halves.
2. Conquer: solve the part(s) you need by calling the same function (recursion).
3. Combine: build the final answer from the parts' answers. (In binary search this step is empty: the half's answer is the answer.)

The teacher places it as a variation of non-linear recursion. "Non-linear" means a function may branch into more than one call. Merge sort really calls both halves. Binary search could go either way, but it picks one side at each step.

2How to recognise it

• The input can be cut into parts that don't share anything (left half / right half of an array).
• Each part is the same kind of problem, only smaller.
• Often the data is sorted, or there's some rule that tells you which part to keep and which to throw away.
• The time usually contains a log n, because the size halves at each level.

3The intuition: why there's no overlap

Take the sorted array [1, 2, 3, 4, 5, 6]. Splitting it gives [1, 2, 3] and [4, 5, 6]. Split those again and you get [1, 2], [3], [4, 5], [6], and so on. Draw all the ranges that could ever be asked:

                 [1 2 3 4 5 6]
                /             \
         [1 2 3]               [4 5 6]
         /     \               /     \
      [1 2]    [3]          [4 5]    [6]
      /   \                 /   \
    [1]   [2]             [4]   [5]

Every box is a different piece of the array. 4, 5 and 6 can never show up inside the left side, and 1, 2, 3 can never show up on the right. So no call ever solves the same sub-problem twice.

Compare it with a recursion that does overlap, like Fibonacci: fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. These repeated calls are why such recursions blow up to about 2ⁿ calls and need DP (storing answers so you don't recompute them). Divide and conquer doesn't have that problem.

Part B · Example: find a target in a sorted array

LeetCode 704 · Binary Search

1The question in simple words

You get an array nums sorted from small to large, and a number target. Return the index (position) of target in nums, or −1 if it isn't there. (If a question only asks "is it present?", return True / False instead. The logic is the same.)

2What the constraints tell us

• 1 ≤ n ≤ 10⁴: the array is never empty. Even O(n) would pass, but the problem wants O(log n).
• All values are unique and sorted in ascending order: sorted is the key word. It lets us throw away half the array after one comparison.
• Values are between −10⁴ and 10⁴: small numbers, nothing special.

3Brute force: linear search

Check every index from left to right until you find the target. In the worst case the target is at the last index (or missing), so you look at all n elements → O(n). This works on any array, sorted or not. It just ignores the fact that ours is sorted.

class Solution:
    def search(self, nums, target):
        for i in range(len(nums)):
            if nums[i] == target:     # found it at index i
                return i
        return -1                     # looked everywhere, not there

4Intuition for binary search

Think of looking up a word in a dictionary. You don't read page by page. You open the middle, see whether your word comes before or after, and ignore the other half completely.

We keep two pointers, left and right, marking the part of the array where the target could still be. Look at the middle index mid:

• nums[mid] == target → found, return mid.
• nums[mid] < target → the target is bigger, so (because the array is sorted) it can only be on the right side → move left.
• nums[mid] > target → the target is smaller, so it can only be on the left side → move right.

5Building the conditions, the way the teacher derives them

Where does mid come from?

mid = left + (right - left) // 2. It's the middle of the current range. With left = 0, right = 5: mid = 0 + 5 // 2 = 2.

nums[mid] < target → left = mid + 1, not mid

Say we want 5 and the middle is 3. The target is bigger, so it lies to the right. The right pointer stays where it is. The left pointer moves. But to mid or mid + 1?

To mid + 1. If nums[mid] were the target, the first check (==) would already have returned it. It didn't, so mid is definitely not the answer and doesn't need to stay in the range.

nums[mid] > target → right = mid - 1

Same reasoning, other side. Say the target is 1 and the middle is bigger. The answer lies to the left, so left stays and right moves to mid − 1 (mid is already ruled out).

The loop condition: left <= right

Left only moves right and right only moves left, so at some point they meet and then cross. The teacher checks three situations:

So the loop runs while left <= right. If it ends without returning, the target was not there → return −1 (or False).

6Approach steps

1. left = 0, right = n − 1.
2. While left ≤ right: mid = left + (right − left) // 2.
3. If nums[mid] == target → return mid.
4. Else if nums[mid] < target → left = mid + 1.
5. Else → right = mid − 1.
6. After the loop → return −1.

7Code (Python)

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:                    # one element left is still valid
            mid = left + (right - left) // 2
            if nums[mid] == target:             # found
                return mid
            elif nums[mid] < target:            # target is on the right
                left = mid + 1
            else:                               # target is on the left
                right = mid - 1
        return -1                               # pointers crossed: not present

8Code line by line

9Dry run (the teacher's example) and complexity

nums = [1, 2, 3, 4, 5, 6], target = 5.

Time. Every round halves the range: n → n/2 → n/4 → n/8 → … → 1. The number of halvings until 1 is log₂ n (base 2 because we cut into 2 halves). So O(log n). Space O(1): just three variables.

Part C · Binary search as divide and conquer recursion

The time won't get better by writing it recursively. The teacher's reasons for doing it anyway: (1) to get used to writing recursive code, and (2) to see a non-linear recursion pattern where sub-problems don't overlap. That pattern is divide and conquer.

1The question

The same as Part B. Now the function receives the range it should search: bs(nums, left, right, target).

2Constraints

n ≤ 10⁴, so the recursion is at most about 15 calls deep, far below Python's limit of ~1000. No setrecursionlimit needed.

3Intuition: what changes when the loop becomes recursion

The teacher's conversion rules:

4Building the base case

In a loop, the while condition is what stops it. Recursion has no loop condition. It keeps calling until we tell it to stop. The loop was valid while left <= right, so we must stop when left > right.

Notice the "found" check is a second stopping point: when nums[mid] == target, we return mid without calling again.

5Approach steps

1. search(nums, target) calls bs(nums, 0, n − 1, target).
2. bs: if left > right → return −1.
3. mid = left + (right − left) // 2.
4. nums[mid] == target → return mid.
5. nums[mid] < target → return bs(nums, mid + 1, right, target).
6. else → return bs(nums, left, mid − 1, target).

6Code (Python)

class Solution:
    def search(self, nums, target):
        return self.bs(nums, 0, len(nums) - 1, target)

    def bs(self, nums, left, right, target):
        if left > right:                        # base case: range empty, not found
            return -1
        mid = left + (right - left) // 2
        if nums[mid] == target:                 # base case: found
            return mid
        elif nums[mid] < target:                # conquer the right half only
            return self.bs(nums, mid + 1, right, target)
        else:                                   # conquer the left half only
            return self.bs(nums, left, mid - 1, target)

7Code line by line

8Dry runs: recursion tree and call stack

Run 1: target found (the teacher's example)

nums = [1, 2, 3, 4, 5, 6], target = 5. Each node shows bs(left, right), its mid, and what it returns. The faded side is the half we never call.

                bs(0,5)  mid=2 (3)  → 4
               /                   \
   bs(0,1) never called         bs(3,5)  mid=4 (5)  → 4   ✓ found

1. bs(0, 5): range not empty. mid = 2, nums[2] = 3 < 5 → call bs(3, 5) and wait. stack: bs(0,5)
2. bs(3, 5): mid = 3 + 1 = 4, nums[4] = 5 == 5 → return 4. Popped.
3. bs(0, 5) receives 4 and returns it unchanged. Popped. Answer 4 ✓.

Run 2: target missing (shows the left == right case and the base case)

nums = [1, 2, 3, 4, 5, 6], target = 7.

bs(0,5)  mid=2 (3 < 7)  → −1
   |  go right
bs(3,5)  mid=4 (5 < 7)  → −1
   |  go right
bs(5,5)  mid=5 (6 < 7)  → −1     ← left == right: still checked
   |  go right
bs(6,5)  left > right   → −1     ← base case

1. bs(0,5): mid 2, 3 < 7 → right half bs(3,5).
2. bs(3,5): mid 4, 5 < 7 → bs(5,5).
3. bs(5,5): one element left. This is why left == right must still be searched: nums[5] = 6 is compared. 6 < 7 → bs(6,5).
4. bs(6,5): left > right, the pointers crossed → return −1.
5. −1 is passed back through bs(5,5), bs(3,5), bs(0,5) unchanged. Answer −1 ✓.

Even though the pattern counts as "non-linear", each call makes at most one call, so what actually runs is a single chain.

9Complexity: counting the calls

• Each call cuts the range at least in half: n → n/2 → n/4 → … → 1 → empty. So there are at most about ⌊log₂ n⌋ + 2 calls (the last one is the empty-range base case).
• Time O(log n): constant work per call. The same as the loop.
• Space O(log n): all those calls wait on the stack. This is the only difference from the loop, which used O(1) space. Recursion uses a stack internally to remember the pending calls.

Part D · Pattern template

Divide and conquer in general (merge sort, which comes next, uses every line):

def solve(data, lo, hi):
    if lo > hi:                       # 1. base case: empty range
        return EMPTY_ANSWER
    if lo == hi:                      #    (or: one element, answer directly)
        return ANSWER_FOR_ONE(data[lo])
    mid = lo + (hi - lo) // 2         # 2. DIVIDE at the middle
    left = solve(data, lo, mid)       # 3. CONQUER each part you NEED
    right = solve(data, mid + 1, hi)  #    (binary search needs only one)
    return COMBINE(left, right)       # 4. COMBINE (binary search: nothing to do)

And the recipe the teacher uses to turn any loop into recursion:

1. Every variable the loop changes (here left and right) → a parameter.
2. The loop condition, flipped (left > right) → the base case, which returns what the code after the loop returned.
3. Each update (left = mid + 1) → a recursive call with the new value as the argument, and return its result.

Her honest tip: you won't write recursive binary search very often. Divide and conquer questions can usually be done with a loop too, and the time is usually the same either way. Learn the recursive version so the pattern feels natural when a problem (like merge sort) really needs both halves.

Part E · Revision page

s = Solution()
print(s.search([1, 2, 3, 4, 5, 6], 5))        # 4
print(s.search([-1, 0, 3, 5, 9, 12], 9))      # 4
print(s.search([-1, 0, 3, 5, 9, 12], 2))      # -1
print(s.search([7], 7))                       # 0
print(s.search([7], 3))                       # -1
print(s.search([1, 2, 3, 4, 5, 6], 7))        # -1

Based on this video: Divide and Conquer Recursion | Binary Search