Binary Search HW

• • 5 min read

Part A:

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

  1. 42
    • 42/2 = 21 R 0
    • 21/2 = 10 R 1
    • 10/2 = 5 R 0
    • 5/2 = 2 R 1
    • 2/2 = 1 R 0
    • 1/2 = ~0 R 1 Binary = 101010
  2. 19
    • 19/2 = 9 R 1
    • 9/2 = 4 R 1
    • 4/2 = 2 R 0
    • 2/2 = 1 R 0
    • 1/2 = ~0 R 1 Binary = 10011
  3. 100
    • 100/2 = 50 R 0
    • 50/2 = 25 R 0
    • 25/2 = 12 R 1
    • 12/2 = 6 R 0
    • 6/2 = 3 R 0
    • 3/2 = 1 R 1
    • 1/2 = ~0 R 1 Binary = 1100100

Part B:

Convert these binary numbers into decimal:

  1. 101010 = (1 * 2^1) + (1 * 2^3) + (1*2^5) = 2 + 8 + 32 = 42
  2. 10011 = (1 * 2^0) + (1 * 2^1) + (1 * 2^4) = 1 + 2 + 16 = 19
  3. 110011 = (1 * 2^0) + (1 * 2^1) + (1 * 2^4) + (1 * 2^5) = 1 + 2 + 16 + 32 = 51

Part C:

Search for 18: Alright, let’s play detective with our sorted list and use binary search to find some numbers!

Our list is: [3,6,9,12,15,18,21,24,27,30,33]

  1. Searching for 18

Step 1: We start by looking at the middle of the list. The list has 11 numbers, so the middle is at index 5, which is 18. We compare 18 (our target) with 18 (the middle). They are equal! Result: Target found! Comparisons: 1

  1. Searching for 33 Step 1: Again, we start with the middle, which is 18. We compare 33 (our target) with 18. 33 is greater than 18, so we know 33 must be in the right half of the list. Step 2: Now we look at the right half: [21,24,27,30,33]. The middle of this is 27. We compare 33 with 27. 33 is greater than 27, so we look at the right half again. Step 3: Now the right half is [30,33]. The middle is 33. We compare 33 with 33. They are equal! Result: Target found! Comparisons: 3

  2. Searching for 5 Step 1: We start with the middle, 18. We compare 5 (our target) with 18. 5 is less than 18, so we look at the left half of the list. Step 2: The left half is [3,6,9,12,15]. The middle number is 9. We compare 5 with 9. 5 is less than 9, so we look at the left half of this sublist. Step 3: The left half is now [3,6]. The middle is 6. We compare 5 with 6. 5 is less than 6. We now look at the left half. Step 4: The left half is now [3]. We compare 5 with 3. 5 is greater than 3. Because there are no more values to check between 3 and 6, we know 5 is not in the list. Result: Target not found! Comparisons: 4

Part D:

[“apple”, “banana”, “carrot”, “dragonfruit”, “fig”, “grape”, “kiwi”, “mango”, “orange”, “peach”, “watermelon”]

  1. Searching for “mango”

Step 1: The middle word is “grape”. “mango” comes after “grape” in the alphabet, so we look at the right half. Step 2: The middle of the right half is “orange”. “mango” comes before “orange” in the alphabet, so we look at the left half of this sublist. Step 3: The middle of this new sublist is “mango”. “mango” matches! Result: Target found! Comparisons: 3

  1. Searching for “carrot”

Step 1: The middle word is “grape”. “carrot” comes before “grape”, so we look at the left half. Step 2: The middle of the left half is “carrot”. “carrot” matches! Result: Target found! Comparisons: 2

  1. Searching for “lemon”

Step 1: The middle word is “grape”. “lemon” comes after “grape”, so we look at the right half. Step 2: The middle of the right half is “orange”. “lemon” comes before “orange”, so we look at the left half of this sublist. Step 3: The middle of this new sublist is “mango”. “lemon” comes before “mango”, so we look at the left half of this sublist. Step 4: The left half of this sublist is “kiwi”. “lemon” comes after “kiwi”, but before “mango”. There are no other values between those two words. Therefore, “lemon” is not in the list. Result: Target not found! Comparisons: 4

Free Response Questions

  1. Why is binary search more efficient for large data than linear search? Binary search cuts the search range in half with each step, making it much faster for large datasets—its time complexity is O(log n) compared to O(n) for linear search. This means it can find items in millions of entries with only a few comparisons.

  2. What happens if the list isn’t sorted and you try to use binary search? Binary search will give incorrect results or fail entirely if the list isn’t sorted, because it relies on the order to decide which half to eliminate. Without sorting, the logic of going left or right based on comparisons breaks down.

  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 for a leaderboard if scores are pre-sorted, making it fast to find a player’s rank. But for a search bar with partial or fuzzy matches, more flexible algorithms like trie searches or inverted indexes are often better.