Skip to content
Deadline to Die

Module 1: Binary Search (The Phone Book)

📚 Module 1: Binary Search

Course ID: DSA-201
Subject: The Phone Book

Imagine you are looking for a name in a physical Phone Book.

  • Linear Search: You start at page 1 and look at every name until you find it. (O(n) - Very Slow).
  • Binary Search: You open to the middle. If the name is “later,” you ignore the whole first half. You repeat this until you find the name. (O(log n) - Incredibly Fast).

🏗️ Step 1: The Requirement (SORTED Data)

Binary Search ONLY works if your data is already Sorted (A to Z, or 1 to 100). If the data is messy, you have to use Linear Search.

🏗️ Step 2: The Divide and Conquer Rule

  1. Find the Middle: Look at the center item.
  2. Compare:
    • Is it the one? Success!
    • Is your target bigger? Discard the Left side.
    • Is your target smaller? Discard the Right side.
  3. Repeat: Focus on the remaining half.

🧩 The Analogy: Guess the Number

I’m thinking of a number between 1 and 100.

  • You guess 50.
  • I say “Higher.”
  • You now know the number is NOT 1 through 50. You just “deleted” 50% of the work in one second!

🏗️ Step 3: Logarithmic Time (O(log n))

Logarithmic time means that even if the data doubles, you only add ONE extra step.

  • 1,000 items? Takes ~10 steps.
  • 1,000,000 items? Takes ~20 steps.
  • 1,000,000,000 items? Takes ~30 steps.

🥅 Module 1 Review

  1. Condition: Data must be sorted.
  2. Strategy: Continually split the data in half.
  3. Complexity: O(log n) - The “Gold Standard” of searching.

:::tip Slow Learner Note Don’t memorize the code. Memorize the Three Pointers: Low, High, and Mid. Everything else is just comparing those three! :::