🎯 HOOK

The Phone Book Challenge

You need to find "Smith" in a phone book with 1,024 pages. You open to the middle, see "Martin", and know Smith comes after. You've just eliminated half the pages. Keep dividing. How many checks?

🧪 EXPLORE

Watch Binary Search in Action

Adjust the array size and search for a number. See how few steps it takes!

Max steps needed: 4

Searching for: ?
Steps Taken
0
Array Size
16
Time
0ms

Amazing: Double the array size, and you only add ONE more step! 16 items = 4 steps. 32 items = 5 steps. That's O(log n)!

💡 EXPLAIN

What is O(log n)?

Logarithmic time means doubling the input only adds one more step.

✂️

Think of it like divide and conquer

  • ✓ Binary search on sorted data
  • ✓ Balanced tree steps
  • ✓ Efficiently finding items in sorted structures
  • ✓ Many divide-and-conquer algorithms
# Binary search (O(log n))
def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Growth Examples

n Steps (log₂ n)
164
1,02410
1,000,000~20

Why It's Powerful

O(log n) scales incredibly well. Even with billions of items, you only need about 30 steps. This is why databases and search engines are so fast!

⚠️ Requirement: Binary search only works on sorted data. If your data isn't sorted, you'd need to sort it first (which is O(n log n)).

✏️ PRACTICE

Test Your Understanding

1. Which operation is O(log n)?

2. Binary search on 256 items takes 8 steps. How many for 512 items?

3. Why doesn't binary search work on unsorted data?

4. Compare: Linear search vs Binary search on 1 million sorted items

5. True or False: O(log n) is always faster than O(n)

6. Which data structure provides O(log n) search?

7. Real-world: Autocomplete suggestions

You type "ap" and see "apple, application, approach". How does the system find matching words efficiently in a dictionary of millions?

🤔 REFLECT

Think Deeper

💭 Why is O(log n) called "logarithmic"?

💭 When would you sort data first (O(n log n)) just to use binary search (O(log n))?

🎉

Fantastic!

You've mastered O(log n) logarithmic time — one of the most elegant and efficient speed classes!