Binary Search Popcorn and HW Hacks
Popcorn Hack 1: Binary Place Value
| Binary Digit | 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|---|---|
| Value | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Binary for 25 |
0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
Fill out the rest of the table and calculate what value is in binary: 00011001
Check answer: 0 + 0 + 0 + (1*16) + (1*8) + 0 + 0 + (1*1) = 16 + 8 + 1 = 25
Popcorn Hack 2: Binary Blitz
Convert 10 to Binary
- 10 ÷ 2 = 5, remainder 0
- 5 ÷ 2 = 2, remainder 1
- 2 ÷ 2 = 1, remainder 0
- 1 ÷ 2 = 0, remainder 1
Remainders from bottom to top:
10 in binary = 1010
Convert 15 to Binary
- 15 ÷ 2 = 7, remainder 1
- 7 ÷ 2 = 3, remainder 1
- 3 ÷ 2 = 1, remainder 1
- 1 ÷ 2 = 0, remainder 1
Remainders from bottom to top:
15 in binary = 1111
Convert 17 to Binary
- 17 ÷ 2 = 8, remainder 1
- 8 ÷ 2 = 4, remainder 0
- 4 ÷ 2 = 2, remainder 0
- 2 ÷ 2 = 1, remainder 0
- 1 ÷ 2 = 0, remainder 1
Remainders from bottom to top:
17 in binary = 10001
Final Answers:
| Decimal | Binary |
|---|---|
| 10 | 1010 |
| 15 | 1111 |
| 17 | 10001 |
Popcorn Hack 3: Half & Half!
To search for the number 18 using binary search, here’s what I’d do:
- Start by checking the middle number in the list: [3, 6, 9, 12, 15, 18, 21, 24].
- The middle is 12. Since 18 is greater than 12, I ignore everything to the left of 12.
- Now I look at the right half: [15, 18, 21, 24]. The new middle is 18.
Using the above, I was able to find 18 in just two steps.
Homework Hacks
PART A: Binary Breakdown
42 → Binary
- Divide by 2 steps:
- 42 ÷ 2 = 21 → 0
- 21 ÷ 2 = 10 → 1
- 10 ÷ 2 = 5 → 0
- 5 ÷ 2 = 2 → 1
- 2 ÷ 2 = 1 → 0
- 1 ÷ 2 = 0 → 1
- Binary result:
101010
Place Value Breakdown: | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ | |—-|—-|—-|—-|—-|—-| | 1 | 0 | 1 | 0 | 1 | 0 |
19 → Binary
- 19 ÷ 2 = 9 → 1
- 9 ÷ 2 = 4 → 1
- 4 ÷ 2 = 2 → 0
- 2 ÷ 2 = 1 → 0
- 1 ÷ 2 = 0 → 1
- Binary:
10011
| 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
100 → Binary
- 100 ÷ 2 = 50 → 0
- 50 ÷ 2 = 25 → 0
- 25 ÷ 2 = 12 → 1
- 12 ÷ 2 = 6 → 0
- 6 ÷ 2 = 3 → 0
- 3 ÷ 2 = 1 → 1
- 1 ÷ 2 = 0 → 1
- Binary:
1100100
| 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
PART B: Binary to Decimal Sprint
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
List: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
Search for 18
- Middle index: 5 →
18- Result Found! - Comparisons: 1
Search for 33
- Mid index: 5 → 18
- 33 > 18 → search right
- Mid index: 8 → 27
- 33 > 27 → search right
- Mid index: 10 → 33 - Result Found!
- Comparisons: 3
Search for 5
- Mid index: 5 → 18
- 5 < 18 → search left
- Mid index: 2 → 9
- 5 < 9 → search left
- Mid index: 0 → 3
- 5 > 3 → no more items
- Comparisons: 3
- Result: Not found
PART D: Binary Search with Strings
List: ["apple", "banana", "carrot", "dragonfruit", "fig", "grape", "kiwi", "mango", "orange", "peach", "watermelon"]
Search for “mango”
- Mid index: 5 → “grape”
- “mango” > “grape” → search right
- Mid: 8 → “orange”
- “mango” < “orange” → search left
- Mid: 6 → “kiwi”
- “mango” > “kiwi” → mid: 7 → “mango” - RESULT FOUND
- Comparisons: 4
Search for “carrot”
- Mid index: 5 → “grape”
- “carrot” < “grape” → search left
- Mid: 2 → “carrot” - RESULT FOUND
- Comparisons: 2
Search for “lemon”
- Mid: 5 → “grape”
- “lemon” > “grape” → search right
- Mid: 8 → “orange”
- “lemon” < “orange” → search left
- Mid: 6 → “kiwi”
- “lemon” > “kiwi” → mid: 7 → “mango”
- “lemon” < “mango” → no more items
- Comparisons: 4
- Result: Not found
EXTRA: Below are code cells to approach parts C and D as well:
def binary_search_steps(arr, target):
left, right = 0, len(arr) - 1
steps = 0
while left <= right:
steps += 1
mid = (left + right) // 2
print(f"Step {steps}: Checking index {mid} -> {arr[mid]}")
if arr[mid] == target:
print(f" Found {target} in {steps} steps.\n")
return
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
print(f" {target} not found after {steps} steps.\n")
# Example list
numbers = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
# Test cases
binary_search_steps(numbers, 18)
binary_search_steps(numbers, 33)
binary_search_steps(numbers, 5)
Step 1: Checking index 5 -> 18
Found 18 in 1 steps.
Step 1: Checking index 5 -> 18
Step 2: Checking index 8 -> 27
Step 3: Checking index 9 -> 30
Step 4: Checking index 10 -> 33
Found 33 in 4 steps.
Step 1: Checking index 5 -> 18
Step 2: Checking index 2 -> 9
Step 3: Checking index 0 -> 3
Step 4: Checking index 1 -> 6
5 not found after 4 steps.
def binary_search_strings(words, target):
left, right = 0, len(words) - 1
steps = 0
while left <= right:
steps += 1
mid = (left + right) // 2
print(f"Step {steps}: Checking index {mid} -> '{words[mid]}'")
if words[mid] == target:
print(f" Found '{target}' in {steps} steps.\n")
return
elif words[mid] < target:
left = mid + 1
else:
right = mid - 1
print(f" '{target}' not found after {steps} steps.\n")
# Sorted string list
word_list = ["apple", "banana", "carrot", "dragonfruit", "fig",
"grape", "kiwi", "mango", "orange", "peach", "watermelon"]
# Test cases
binary_search_strings(word_list, "mango")
binary_search_strings(word_list, "carrot")
binary_search_strings(word_list, "lemon")
Step 1: Checking index 5 -> 'grape'
Step 2: Checking index 8 -> 'orange'
Step 3: Checking index 6 -> 'kiwi'
Step 4: Checking index 7 -> 'mango'
Found 'mango' in 4 steps.
Step 1: Checking index 5 -> 'grape'
Step 2: Checking index 2 -> 'carrot'
Found 'carrot' in 2 steps.
Step 1: Checking index 5 -> 'grape'
Step 2: Checking index 8 -> 'orange'
Step 3: Checking index 6 -> 'kiwi'
Step 4: Checking index 7 -> 'mango'
'lemon' not found after 4 steps.
FRQ QUESTIONS:
1. Why is binary search more efficient for large data than linear search?
Binary search is more efficient because it cuts the search space in half with each step, instead of checking each item one by one like linear search. This means it can find an item in a list of a million elements in about 20 steps, while linear search could take up to a million. Its time complexity is O(log N), which grows much slower than O(N). This makes it ideal for large datasets that are already sorted.
2. 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 because it relies on knowing whether to search the left or right half. Without order, it might go in the wrong direction and miss the target completely. You might get incorrect results or not find the item at all. That’s why sorting is a required condition for using binary search.
3. Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?
Yes, binary search could be used in a video game leaderboard or search bar, but only if the data is sorted. For example, if a leaderboard is sorted by score or username, binary search can quickly find a player’s rank. Streaming services also sort titles alphabetically or by category, making binary search useful to quickly locate content. However, if the list isn’t sorted or changes often, a different search method might be better.