Binary Search Algorithm Homework and Popcorn Hacks #25
Description
💻 Binary Breakdown + Binary Search Practice
🔢 PART A: Binary Breakdown
Convert the following decimals to binary:
🔸 42
Division-by-2 Steps:
42 ÷ 2 = 21 remainder 0
21 ÷ 2 = 10 remainder 1
10 ÷ 2 = 5 remainder 0
5 ÷ 2 = 2 remainder 1
2 ÷ 2 = 1 remainder 0
1 ÷ 2 = 0 remainder 1
Binary: 101010
Place Value Table:
| 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
🧮 32 + 8 + 2 = 42
🔸 19
Division-by-2 Steps:
19 ÷ 2 = 9 remainder 1
9 ÷ 2 = 4 remainder 1
4 ÷ 2 = 2 remainder 0
2 ÷ 2 = 1 remainder 0
1 ÷ 2 = 0 remainder 1
Binary: 10011
Place Value Table:
| 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
🧮 16 + 2 + 1 = 19
🔸 100
Division-by-2 Steps:
100 ÷ 2 = 50 remainder 0
50 ÷ 2 = 25 remainder 0
25 ÷ 2 = 12 remainder 1
12 ÷ 2 = 6 remainder 0
6 ÷ 2 = 3 remainder 0
3 ÷ 2 = 1 remainder 1
1 ÷ 2 = 0 remainder 1
Binary: 1100100
Place Value Table:
| 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
🧮 64 + 32 + 4 = 100
💡 PART B: Binary to Decimal Sprint
🔸 101010
| 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
🧮 32 + 8 + 2 = 42
Decimal: 42
🔸 10011
| 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
🧮 16 + 2 + 1 = 19
Decimal: 19
🔸 110011
| 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 |
🧮 32 + 16 + 2 + 1 = 51
Decimal: 51
🔎 PART C: Binary Search in Action
List: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
🔸 Search for 18
Steps:
- low=0, high=10, mid=5 → list[5]=18 ✅ Found!
🔁 Comparisons: 1
📌 Result: Found at index 5
🔸 Search for 33
Steps:
- low=0, high=10, mid=5 → 18
- 33 > 18 → low=6
- mid=8 → 27
- 33 > 27 → low=9
- mid=9 → 30
- 33 > 30 → low=10
- mid=10 → 33 ✅ Found!
🔁 Comparisons: 4
📌 Result: Found at index 10
🔸 Search for 5
Steps:
- mid=5 → 18
- 5 < 18 → high=4
- mid=2 → 9
- 5 < 9 → high=1
- mid=0 → 3
- 5 > 3 → low=1
- mid=1 → 6
- 5 < 6 → high=0
Now low > high ❌ Not Found
🔁 Comparisons: 5
📌 Result: Not in list
🔠 PART D: Binary Search with Strings
List:
["apple", "banana", "carrot", "dragonfruit", "fig", "grape", "kiwi", "mango", "orange", "peach", "watermelon"]
🔸 Search for "mango"
- mid=5 → "grape"
- "mango" > "grape" → low=6
- mid=8 → "orange"
- "mango" < "orange" → high=7
- mid=6 → "kiwi"
- "mango" > "kiwi" → low=7
- mid=7 → "mango" ✅ Found
🔁 Comparisons: 4
📌 Result: Found
🔸 Search for "carrot"
- mid=5 → "grape"
- "carrot" < "grape" → high=4
- mid=2 → "carrot" ✅ Found
🔁 Comparisons: 2
📌 Result: Found
🔸 Search for "lemon"
- mid=5 → "grape"
- "lemon" > "grape" → low=6
- mid=8 → "orange"
- "lemon" < "orange" → high=7
- mid=6 → "kiwi"
- "lemon" > "kiwi" → low=7
- mid=7 → "mango"
- "lemon" < "mango" → high=6
Now low > high ❌ Not Found
🔁 Comparisons: 5
📌 Result: Not in list
🧠 Free Response
✅ Why is binary search more efficient than linear search?
Binary search halves the search space with every step, reducing time complexity to O(log n), which is much faster for large datasets compared to linear search’s O(n).
✅ What happens if the list isn’t sorted and you try to use binary search?
If the list isn’t sorted, binary search won’t work correctly — it may miss the item or return wrong results, because it depends on the data being ordered.
✅ Could you use binary search in a video game leaderboard or streaming service search bar?
Yes, if the data (like names or scores) is sorted, binary search can make lookups super fast, which is perfect for live, responsive systems like leaderboards or search bars.
🍿 Bonus: Popcorn Hacks
🍿 Popcorn Hack 1: Binary Table (25)
Binary for 25 = 11001
| 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
🧮 16 + 8 + 1 = 25
🍿 Popcorn Hack 2: Binary Blitz
- 10 →
1010 - 15 →
1111 - 17 →
10001
🍿 Popcorn Hack 3: Half & Half!
List: [3, 6, 9, 12, 15, 18, 21, 24]
Search for: 18
Steps:
- mid=3 → 12 → too small
- mid=5 → 18 ✅
📌 Answer: Found in 2 comparisons