Binary Search
HW Hacks
Popcorn Hack 1
Binary Place Value Table
| Binary Digit | 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|---|---|
| Example: 1101 | 1 | 1 | 0 | 1 | ||||
| New Example | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
Calculation for 25:
- 1×2⁴ (16) + 1×2³ (8) + 0×2² (0) + 0×2¹ (0) + 1×2⁰ (1)
- = 16 + 8 + 0 + 0 + 1
- = 25
Thus, 25 in binary = 00011001!
Popcorn Hack #2: Binary Blitz!
Convert the following decimals into binary:
10 in Binary
- 2³ = 8 (10 - 8 = 2)
- 2¹ = 2 (2 - 2 = 0)
| Binary Digit | 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
10 in binary = 00001010
15 in Binary
- 2³ = 8 (15 - 8 = 7)
- 2² = 4 (7 - 4 = 3)
- 2¹ = 2 (3 - 2 = 1)
- 2⁰ = 1 (1 - 1 = 0)
| Binary Digit | 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
15 in binary = 00001111
17 in Binary
- 2⁴ = 16 (17 - 16 = 1)
- 2⁰ = 1 (1 - 1 = 0)
| Binary Digit | 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
17 in binary = 00010001
Quick Recap
| Decimal | Binary |
|:——-:|:———-:|
| 10 | 00001010 |
| 15 | 00001111 |
| 17 | 00010001 |
Popcorn Hack 3
Final Answer: Use Binary Search
Answer:
Use Binary Search because it would be faster.
Reason:
- The list
[3, 6, 9, 12, 15, 18, 21, 24]is already sorted. - Binary Search cuts the list in half each step, quickly narrowing down where the number is.
- Linear Search checks one number at a time from the start, which takes more steps.
- In this case:
- Binary Search would find 18 in about 2 steps.
- Linear Search would take about 6 steps.
Conclusion:
Binary Search is faster on sorted lists because it dramatically reduces the number of comparisons needed.
PART A: Binary Breakdown
Convert the following decimal numbers into binary, and explain the place values used.
1. Convert 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 Result
101010
Place Value Breakdown
| 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ | |:–:|:–:|:–:|:–:|:–:|:–:| | 1 | 0 | 1 | 0 | 1 | 0 |
32 + 0 + 8 + 0 + 2 + 0 = 42
2. Convert 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 Result
10011
Place Value Breakdown
| 2⁴ | 2³ | 2² | 2¹ | 2⁰ | |:–:|:–:|:–:|:–:|:–:| | 1 | 0 | 0 | 1 | 1 |
16 + 0 + 0 + 2 + 1 = 19
3. Convert 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 Result
1100100
Place Value Breakdown
| 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ | |:–:|:–:|:–:|:–:|:–:|:–:|:–:| | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
64 + 32 + 0 + 0 + 4 + 0 + 0 = 100
PART B: Binary to Decimal Sprint
Convert these binary numbers into decimal.
1. 101010
| 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
32 + 0 + 8 + 0 + 2 + 0 = 42
2. 10011
| 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
16 + 0 + 0 + 2 + 1 = 19
3. 110011
| 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 |
32 + 16 + 0 + 0 + 2 + 1 = 51
PART C: Binary Search in Action
Given the list:
1. Search for 18
- Middle index: (0+10) ÷ 2 = 5 → 18
- 18 == 18 → Found
Comparisons made: 1
Result: Found
2. Search for 33
- Middle index: 5 → 18
- 33 > 18 → search right half [21, 24, 27, 30, 33]
- Middle index: 8 → 27
- 33 > 27 → search right half [30, 33]
- Middle index: 9 → 30
- 33 > 30 → search right half [33]
- Index 10 → 33
Comparisons made: 4
Result: Found
3. Search for 5 (not in list)
- Middle index: 5 → 18
- 5 < 18 → search left half [3, 6, 9, 12, 15]
- Middle index: 2 → 9
- 5 < 9 → search left half [3, 6]
- Middle index: 0 → 3
- 5 > 3 → search right half [6]
- Middle index: 1 → 6
- 5 < 6 → no more numbers
Comparisons made: 5
Result: Not found
PART D: Binary Search with Strings
Given the list:
1. Search for “mango”
- Middle index: 5 → “grape”
- “mango” > “grape” → search right half
- Middle index: 8 → “orange”
- “mango” < “orange” → search left half
- Middle index: 6 → “kiwi”
- “mango” > “kiwi” → search right half
- Index 7 → “mango”
Comparisons made: 4
Result: Found
2. Search for “carrot”
- Middle index: 5 → “grape”
- “carrot” < “grape” → search left half
- Middle index: 2 → “carrot”
Comparisons made: 2
Result: Found
3. Search for “lemon” (not in list)
- Middle index: 5 → “grape”
- “lemon” > “grape” → search right half
- Middle index: 8 → “orange”
- “lemon” < “orange” → search left half
- Middle index: 6 → “kiwi”
- “lemon” > “kiwi” → search right half
- No “lemon” found between “kiwi” and “mango”
Comparisons made: 4
Result: Not found
Free Response Questions
1. Why is binary search more efficient for large data than linear search?
Binary search is faster because it cuts the number of items to search in half with each step, making it much quicker for large datasets.
2. What happens if the list isn’t sorted and you try to use binary search?
Binary search would fail if the list is not sorted, because it relies on the assumption that smaller elements are on one side and larger elements are on the other.
3. Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?
Yes, you could use binary search if the leaderboard or list of titles is sorted. This would allow fast lookup times for player scores or movie names.