Course contentsShow
← Computer Science
Lesson 844 of 2,87220. Recursion Patterns and TechniquesFree lesson

Binary Search as Divide and Conquer

Analyzing binary search through the divide and conquer lens: dividing sorted array in half each step.

Binary Search as Divide and Conquer

What you'll learn: How binary search exemplifies the divide-and-conquer paradigm by repeatedly splitting a sorted array in half.

The Divide-and-Conquer Pattern

You've seen binary search before as a searching technique, but now let's view it through the lens of divide and conquer. Binary search perfectly demonstrates this paradigm's three essential steps:

  1. Divide: Split the sorted array at the middle point
  2. Conquer: Determine which half contains the target (if any)
  3. Combine: In binary search, there's nothing to combine—the answer comes directly from the recursive search

How It Works

When searching for a value in a sorted array, binary search doesn't look at every element. Instead, it checks the middle element and makes a decision: "Is my target in the left half or the right half?" Then it repeats this process on only that half.

Think of it like a phone book: If you're looking for "Martinez," you open to the middle. If you land on "Johnson," you know Martinez must be in the right half—so you ignore the entire left half and repeat the process.

The Recurrence Relation

Binary search creates a simple recurrence relation:

  • Each step processes one comparison (constant work)
  • Then recursively searches one half of the remaining space

This gives us T(n) = T(n/2) + O(1), which solves to O(log n) time complexity—the problem size shrinks by half each step, leading to logarithmic depth.

Key Takeaway: Binary search is a classic divide-and-conquer algorithm that achieves O(log n) performance by dividing the problem space in half at each step, requiring no combination phase since the recursive call directly yields the answer.