🧠 Binary Search Algorithm - Team Teach Hacks & Homework

🍿 Popcorn Hack #1: Binary Value Table

Fill in the binary place value table to get the value 25:

Binary Digit 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Value 128 64 32 16 8 4 2 1
Example: 11001     1 1 0 0 0 1

➡ 1×16 + 1×8 + 0×4 + 0×2 + 1×1 = 25

🍿 Popcorn Hack #2: Binary Blitz!

Convert the following decimal numbers to binary:

  • 10 → 1010
    • 10 ÷ 2 = 5 R0
    • 5 ÷ 2 = 2 R1
    • 2 ÷ 2 = 1 R0
    • 1 ÷ 2 = 0 R1
    • Binary: 1010
  • 15 → 1111
    • 15 ÷ 2 = 7 R1
    • 7 ÷ 2 = 3 R1
    • 3 ÷ 2 = 1 R1
    • 1 ÷ 2 = 0 R1
    • Binary: 1111
  • 17 → 10001
    • 17 ÷ 2 = 8 R1
    • 8 ÷ 2 = 4 R0
    • 4 ÷ 2 = 2 R0
    • 2 ÷ 2 = 1 R0
    • 1 ÷ 2 = 0 R1
    • Binary: 10001

🍿 Popcorn Hack #3: Half & Half!

Given: [3, 6, 9, 12, 15, 18, 21, 24]
Target: 18

  1. Check middle: index 3 → 12
  2. 18 > 12 → Search right half [15, 18, 21, 24]
  3. New middle: index 5 → 18 ✅ Found!
    Steps: 2 comparisons

🏠 HOMEWORK HACK

🧠 PART A: Binary Breakdown

Convert 42 to Binary

  • 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

Breakdown: 1×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1 = 42

Convert 19 to Binary

  • 19 ÷ 2 = 9 R1
  • 9 ÷ 2 = 4 R1
  • 4 ÷ 2 = 2 R0
  • 2 ÷ 2 = 1 R0
  • 1 ÷ 2 = 0 R1
    → Binary: 10011

Breakdown: 1×16 + 0×8 + 0×4 + 1×2 + 1×1 = 19

Convert 100 to Binary

  • 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

Breakdown: 1×64 + 1×32 + 0×16 + 0×8 + 1×4 + 0×2 + 0×1 = 100

💡 PART B: Binary to Decimal Sprint

Convert 101010 to Decimal

1×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1 = 42

Convert 10011 to Decimal

1×16 + 0×8 + 0×4 + 1×2 + 1×1 = 19

Convert 110011 to Decimal

1×32 + 1×16 + 0×8 + 0×4 + 1×2 + 1×1 = 51

🔎 PART C: Binary Search in Action

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

Search for 18

  1. Middle index 5 → 18 ✅ Found
    Comparisons: 1

Search for 33

  1. Middle index 5 → 18
  2. 33 > 18 → Right half
  3. Middle index 8 → 27
  4. 33 > 27 → Right half
  5. Middle index 10 → 33 ✅ Found
    Comparisons: 3

Search for 5

  1. Middle index 5 → 18
  2. 5 < 18 → Left half
  3. Middle index 2 → 9
  4. 5 < 9 → Left half
  5. Middle index 0 → 3
  6. 5 > 3 → Right half
  7. Middle index 1 → 6
  8. 5 < 6 → Left half → Empty
    Comparisons: 4
    Not found

🔠 PART D: Binary Search with Strings

Given:
["apple", "banana", "carrot", "dragonfruit", "fig", "grape", "kiwi", "mango", "orange", "peach", "watermelon"]

Search for “mango”

  1. Middle index 5 → “grape”
  2. “mango” > “grape” → Right half
  3. Middle index 8 → “orange”
  4. “mango” < “orange” → Left half
  5. Middle index 6 → “kiwi”
  6. “mango” > “kiwi” → Right half
  7. Middle index 7 → “mango” ✅ Found
    Comparisons: 4

Search for “carrot”

  1. Middle index 5 → “grape”
  2. “carrot” < “grape” → Left half
  3. Middle index 2 → “carrot” ✅ Found
    Comparisons: 2

Search for “lemon”

  1. Middle index 5 → “grape”
  2. “lemon” > “grape” → Right half
  3. Middle index 8 → “orange”
  4. “lemon” < “orange” → Left half
  5. Middle index 6 → “kiwi”
  6. “lemon” > “kiwi” → Right half
  7. Middle index 7 → “mango”
  8. “lemon” < “mango” → Left half → Empty
    Comparisons: 4
    Not found

✅ Free Response Questions

Q1: Why is binary search more efficient for large data than linear search?
Binary search reduces the search space by half with each step, giving it a time complexity of O(log n), making it much faster than linear search which checks each element one by one (O(n)).

Q2: What happens if the list isn’t sorted and you try to use binary search?
If the list isn’t sorted, binary search can give incorrect results or fail entirely since it depends on comparing the target to middle elements to discard half the list.

Q3: Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?
Yes, as long as the data (like player scores or titles) is sorted, binary search would be fast and efficient for quickly locating specific entries in large datasets.