3.1 Binary Search Algorithm

Big Idea 3.1

• 5 min read

Big Idea3

📝 PART 1: Notes

🧩 What Is Binary and Why Does It Matter?

🔢 What is Binary?

  • Binary is a Base-2 number system made up of only 0 and 1.
  • Computers process binary to represent all types of data: text, images, video, music, and logic.
  • One bit = 1 digit (0 or 1)
  • One byte = 8 bits → Can represent 256 values

🌍 Real-World Use Cases

  • Images store pixel data using binary (e.g., RGB color codes)
  • Text uses ASCII or Unicode to map characters to binary (e.g., "A" = 01000001)
  • Music and videos are stored and transmitted as binary streams

🧠 Binary Place Value Table

Binary Digit 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Example: 1101 1 1 0 1        

➡️ 1×8 + 1×4 + 0×2 + 1×1 = 13

🔄 Converting Between Binary & Decimal

🔁 Decimal to Binary (Divide by 2 Method)

Steps:

  1. Divide number by 2
  2. Record the remainder
  3. Repeat until quotient is 0
  4. Read remainders bottom to top

Example: Convert 25 25 ÷ 2 = 12 R1 12 ÷ 2 = 6 R0 6 ÷ 2 = 3 R0 3 ÷ 2 = 1 R1 1 ÷ 2 = 0 R1

➡️ Binary: 11001

🔁 Binary to Decimal

Example: 1101 = 1×8 + 1×4 + 0×2 + 1×1 = 13

🔍 Binary Search vs Linear Search

📘 What is Binary Search?

Binary Search is a powerful algorithm for searching a sorted list by cutting the search space in half repeatedly.

Steps:

  • Check middle element
  • If it matches, return it
  • Else decide to search left or right half
  • Repeat until found or empty

⚖️ Comparison Table

Feature Binary Search Linear Search
Requires sorted? ✅ Yes ❌ No
Speed (steps) Fast – log₂(n) Slow – up to n steps
Example (100 items) ~7 steps Up to 100 steps
Best for… Large, sorted Small or unsorted

⏱️ Time Complexity

  • Cuts list in half each time
  • Time complexity: O(log₂ n)
  • Faster than linear search: O(n)

✅ PART 2: Completed Hacks

🍿 Popcorn Hack #1 — Binary Value of 25

Binary Digit 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Value 0 0 0 1 1 0 0 1

16 + 8 + 1 = 25 → 11001

🍿 Popcorn Hack #2 — Decimal to Binary

  • 10 → 1010
  • 15 → 1111
  • 17 → 10001

🍿 Popcorn Hack #3 — Find 18 in List

List: [3, 6, 9, 12, 15, 18, 21, 24]
Steps:

  1. mid = index 3 → 12
  2. 18 > 12 → search right
  3. mid = index 5 → 18 ✅ Found in 2 comparisons

🏠 HOMEWORK HACKS

🧠 PART A: Binary Breakdown

1. Convert the following decimal numbers into binary:

  • 42
    • Division steps: 
      42 ÷ 2 = 21 R0  
21 ÷ 2 = 10 R1  
10 ÷ 2 = 5 R0  
5 ÷ 2 = 2 R1  
2 ÷ 2 = 1 R0  
1 ÷ 2 = 0 R1  
→ Binary: 101010
    • Place values:
      • 1×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1 = 42
  • 19
    • Division steps: 
      19 ÷ 2 = 9 R1  
9 ÷ 2 = 4 R1  
4 ÷ 2 = 2 R0  
2 ÷ 2 = 1 R0  
1 ÷ 2 = 0 R1  
→ Binary: 10011
    • Place values:
      • 1×16 + 0×8 + 0×4 + 1×2 + 1×1 = 19
  • 100
    • Division steps: 
      100 ÷ 2 = 50 R0  
50 ÷ 2 = 25 R0  
25 ÷ 2 = 12 R1  
12 ÷ 2 = 6 R0  
6 ÷ 2 = 3 R0  
3 ÷ 2 = 1 R1  
1 ÷ 2 = 0 R1  
→ Binary: 1100100
    • Place values:
      • 1×64 + 1×32 + 0×16 + 0×8 + 1×4 + 0×2 + 0×1 = 100

💡 PART B: Binary to Decimal Sprint

Convert these binary numbers into decimal:

  • 101010
    • 1×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1 = 42
  • 10011
    • 1×16 + 0×8 + 0×4 + 1×2 + 1×1 = 19
  • 110011
    • 1×32 + 1×16 + 0×8 + 0×4 + 1×2 + 1×1 = 51

🔎 PART C: Binary Search in Action

Sorted List:
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]

  • Search for 18
    • Step 1: mid=5 → 18 ✅
    • Comparisons: 1
  • Search for 33
    • Step 1: mid=5 → 18
    • Step 2: mid=8 → 27
    • Step 3: mid=10 → 33 ✅
    • Comparisons: 3
  • Search for 5
    • Step 1: mid=5 → 18
    • Step 2: mid=2 → 9
    • Step 3: mid=0 → 3
    • Step 4: mid=1 → 6
    • Not found ❌
    • Comparisons: 4

🔠 PART D: Binary Search with Strings

Sorted List of Words:
["apple", "banana", "carrot", "dragonfruit", "fig", "grape", "kiwi", "mango", "orange", "peach", "watermelon"]

  • Search for “mango”
    • Step 1: mid=5 → “grape”
    • Step 2: mid=8 → “orange”
    • Step 3: mid=7 → “mango” ✅
    • Comparisons: 3
  • Search for “carrot”
    • Step 1: mid=5 → “grape”
    • Step 2: mid=2 → “carrot” ✅
    • Comparisons: 2
  • Search for “lemon”
    • Step 1: mid=5 → “grape”
    • Step 2: mid=8 → “orange”
    • Step 3: mid=6 → “kiwi”
    • Step 4: mid=7 → “mango”
    • Not found ❌
    • Comparisons: 4

✅ Free Response Questions

  1. Why is binary search more efficient for large data than linear search?
    Binary search divides the dataset in half at every step, reducing the number of comparisons. This makes it logarithmic in time complexity, unlike linear search which has to check every element one by one.

  2. What happens if the list isn’t sorted and you try to use binary search?
    Binary search will not work correctly on unsorted data. It relies on the data being in order to eliminate half of the possibilities each time.

  3. Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?
    Yes, if the leaderboard or search index is sorted (e.g., alphabetically or by score), binary search can help quickly find entries and improve search performance.