Popcorn Hack 1

Fill out the rest of the table and calculate what value is in binary: (final value should be 25)

Binary Digit 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Number (25) 0 0 0 1 1 0 0 1
Value 0 0 0 16 8 0 2 1
Total 25              

Popcorn Hack 2

Convert the following decimals into binary: 10, 15, 17

Decimal Binary
10 1010
15 1111
17 10001

Homework Hack A

Convert the following decimal numbers into binary, and then explain the place values used:

42 19 100 For each one:

Show the division-by-2 steps Show the binary result Break it down using the place value table

Decimal: 42

  1. 42 / 2 = 21 remainder 0
  2. 21 / 2 = 10 remainder 1
  3. 10 / 2 = 5 remainder 0
  4. 5 / 2 = 2 remainder 1
  5. 2 / 2 = 1 remainder 0
  6. 1 / 2 = 0 remainder 1
  7. Read the remainders from bottom to top: 101010 | Binary Digit | 2⁷ | 2⁶ | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ | |————–|—-|—-|—-|—-|—-|—-|—-|—-| | Number (42) | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | | Value | 0 | 64 | 0 | 16 | 0 | 4 | 0 | 0 | | Total | 42 | | | | | | | |

Decimal: 19

  1. 19 / 2 = 9 remainder 1
  2. 9 / 2 = 4 remainder 1
  3. 4 / 2 = 2 remainder 0
  4. 2 / 2 = 1 remainder 0
  5. 1 / 2 = 0 remainder 1
  6. Read the remainders from bottom to top: 10011
Binary Digit 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Number (19) 0 0 0 0 1 0 0 1
Value 0 0 0 0 16 0 2 1
Total 19              

Decimal: 100

  1. 100 / 2 = 50 remainder 0
  2. 50 / 2 = 25 remainder 0
  3. 25 / 2 = 12 remainder 1
  4. 12 / 2 = 6 remainder 0
  5. 6 / 2 = 3 remainder 0
  6. 3 / 2 = 1 remainder 1
  7. 1 / 2 = 0 remainder 1
  8. Read the remainders from bottom to top: 1100100
Binary Digit 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Number (100) 0 1 1 0 0 1 0 0
Value 0 64 32 0 0 4 0 0
Total 100              

Homework Hack B

💡 PART B: Binary to Decimal Sprint Convert these binary numbers into decimal:

101010 10011 110011 Explain the place values and your math for each!

Binary: 101010

  1. 1 * 2⁵ = 32
  2. 0 * 2⁴ = 0
  3. 1 * 2³ = 8
  4. 0 * 2² = 0
  5. 1 * 2¹ = 2
  6. 0 * 2⁰ = 0
  7. Add them up: 32 + 0 + 8 + 0 + 2 + 0 = 42
  8. Final result: 42

Binary: 10011

  1. 1 * 2⁴ = 16
  2. 0 * 2³ = 0
  3. 0 * 2² = 0
  4. 1 * 2¹ = 2
  5. 1 * 2⁰ = 1
  6. Add them up: 16 + 0 + 0 + 2 + 1 = 19
  7. Final result: 19

Binary: 110011

  1. 1 * 2⁵ = 32
  2. 1 * 2⁴ = 16
  3. 0 * 2³ = 0
  4. 0 * 2² = 0
  5. 1 * 2¹ = 2
  6. 1 * 2⁰ = 1
  7. Add them up: 32 + 16 + 0 + 0 + 2 + 1 = 51
  8. Final result: 51

Homework Hack C

You’re given a sorted list: [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]

Tasks:

Search for 18 Search for 33 Search for 5 (not in list!) For each:

Show the steps taken during the binary search How many comparisons were made? Was the target found or not?

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    comparisons = 0
    steps = []
    while left <= right:
        mid = (left + right) // 2
        comparisons += 1
        steps.append(f"Comparing {target} with {arr[mid]} at index {mid}")
        if arr[mid] == target:
            return True, comparisons, steps
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False, comparisons, steps

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    comparisons = 0
    steps = []
    while left <= right:
        mid = (left + right) // 2
        comparisons += 1
        steps.append(f"Comparing {target} with {arr[mid]} at index {mid}")
        if arr[mid] == target:
            return True, comparisons, steps
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False, comparisons, steps

if __name__ == "__main__":
    arr = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
    target = int(input("Enter the number to search: "))
    found, comparisons, steps = binary_search(arr, target)
    if found:
        print(f"Number {target} found in {comparisons} comparisons.")
    else:
        print(f"Number {target} not found in {comparisons} comparisons.")
    print("Steps taken:")
    for step in steps:
        print(step)

Number 3 found in 3 comparisons.
Steps taken:
Comparing 3 with 18 at index 5
Comparing 3 with 9 at index 2
Comparing 3 with 3 at index 0

Homework Hack D

You’re given a sorted list of words: [“apple”, “banana”, “carrot”, “dragonfruit”, “fig”, “grape”, “kiwi”, “mango”, “orange”, “peach”, “watermelon”]

Tasks:

Search for “mango” Search for “carrot” Search for “lemon” (not in list!) For each:

Simulate binary search steps Show each comparison made How many comparisons until found (or not found)?

def binary_search_words(arr, target):
    left, right = 0, len(arr) - 1
    comparisons = 0
    steps = []
    while left <= right:
        mid = (left + right) // 2
        comparisons += 1
        steps.append(f"Comparing '{target}' with '{arr[mid]}' at index {mid}")
        if arr[mid] == target:
            return True, comparisons, steps
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False, comparisons, steps

def binary_search_words(arr, target):
    left, right = 0, len(arr) - 1
    comparisons = 0
    steps = []
    while left <= right:
        mid = (left + right) // 2
        comparisons += 1
        steps.append(f"Comparing '{target}' with '{arr[mid]}' at index {mid}")
        if arr[mid] == target:
            return True, comparisons, steps
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False, comparisons, steps

if __name__ == "__main__":
    arr = ["apple", "banana", "carrot", "dragonfruit", "fig", "grape", "kiwi", "mango", "orange", "peach", "watermelon"]
    target = input("Enter the word to search: ")
    found, comparisons, steps = binary_search_words(arr, target)
    if found:
        print(f"Word '{target}' found in {comparisons} comparisons.")
    else:
        print(f"Word '{target}' not found in {comparisons} comparisons.")
    print("Steps taken:")
    for step in steps:
        print(step)
# This code implements a binary search algorithm for both numbers and words.
# It includes detailed steps and comparisons made during the search process.
# The user can input a number or a word to search in the respective sorted lists.

Word 'mango' found in 4 comparisons.
Steps taken:
Comparing 'mango' with 'grape' at index 5
Comparing 'mango' with 'orange' at index 8
Comparing 'mango' with 'kiwi' at index 6
Comparing 'mango' with 'mango' at index 7

Homework Hack E

Why is binary search more efficient for large data than linear search? What happens if the list isn’t sorted and you try to use binary search? Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?

Binary search is more efficient for large data sets because it reduces the search space by half with each comparison, leading to a time complexity of O(log n). In contrast, linear search has a time complexity of O(n), meaning it checks each element one by one.

If the list isn’t sorted, binary search cannot be applied effectively because it relies on the order of elements to eliminate half of the search space. In an unsorted list, the algorithm may skip over potential matches.

In a video game leaderboard or streaming service search bar, binary search can be used effectively if the data is sorted (e.g., player scores or titles). However, if the data is not sorted, a linear search would be necessary to find matches, which would be less efficient.