Binary_search_ipynb_2_

• 5 min read

🧠 PART A: Binary Breakdown

1. Convert 42 to binary:

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:
42 = 101010

Place value breakdown: Starting from the rightmost bit (least significant bit):

  • ( 1 \times 2^5 = 32 )
  • ( 0 \times 2^4 = 0 )
  • ( 1 \times 2^3 = 8 )
  • ( 0 \times 2^2 = 0 )
  • ( 1 \times 2^1 = 2 )
  • ( 0 \times 2^0 = 0 )

So, ( 32 + 8 + 2 = 42 ).

2. Convert 19 to binary:

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:
19 = 10011

Place value breakdown:

  • ( 1 \times 2^4 = 16 )
  • ( 0 \times 2^3 = 0 )
  • ( 0 \times 2^2 = 0 )
  • ( 1 \times 2^1 = 2 )
  • ( 1 \times 2^0 = 1 )

So, ( 16 + 2 + 1 = 19 ).

3. Convert 100 to binary:

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:
100 = 1100100

Place value breakdown:

  • ( 1 \times 2^6 = 64 )
  • ( 1 \times 2^5 = 32 )
  • ( 0 \times 2^4 = 0 )
  • ( 0 \times 2^3 = 0 )
  • ( 1 \times 2^2 = 4 )
  • ( 0 \times 2^1 = 0 )
  • ( 0 \times 2^0 = 0 )

So, ( 64 + 32 + 4 = 100 ).

đź’ˇ PART B: Binary to Decimal Sprint

1. Convert 101010 to decimal:

  • ( 1 \times 2^5 = 32 )
  • ( 0 \times 2^4 = 0 )
  • ( 1 \times 2^3 = 8 )
  • ( 0 \times 2^2 = 0 )
  • ( 1 \times 2^1 = 2 )
  • ( 0 \times 2^0 = 0 )

Decimal result = 42

2. Convert 10011 to decimal:

  • ( 1 \times 2^4 = 16 )
  • ( 0 \times 2^3 = 0 )
  • ( 0 \times 2^2 = 0 )
  • ( 1 \times 2^1 = 2 )
  • ( 1 \times 2^0 = 1 )

Decimal result = 19

3. Convert 110011 to decimal:

  • ( 1 \times 2^5 = 32 )
  • ( 1 \times 2^4 = 16 )
  • ( 0 \times 2^3 = 0 )
  • ( 0 \times 2^2 = 0 )
  • ( 1 \times 2^1 = 2 )
  • ( 1 \times 2^0 = 1 )

Decimal result = 51

🔎 PART C: Binary Search in Action

Search for 18:

  • Start with the middle element (index 5, value 18).
  • Target found in 1 comparison.

Search for 33:

  • Start with the middle element (index 5, value 18).
  • Move to the right half, middle element (index 8, value 27).
  • Move to the right again, middle element (index 9, value 33).
  • Target found in 3 comparisons.

Search for 5 (not in list):

  • Start with the middle element (index 5, value 18).
  • Move to the left half, middle element (index 2, value 9).
  • Move to the left again, middle element (index 0, value 3).
  • No further movement, target not found in 3 comparisons.

đź”  PART D: Binary Search with Strings

Search for “mango”:

  • Start with the middle element (index 5, value “grape”).
  • Move to the right half, middle element (index 7, value “mango”).
  • Target found in 2 comparisons.

Search for “carrot”:

  • Start with the middle element (index 5, value “grape”).
  • Move to the left half, middle element (index 2, value “carrot”).
  • Target found in 2 comparisons.

Search for “lemon” (not in list):

  • Start with the middle element (index 5, value “grape”).
  • Move to the left half, middle element (index 2, value “carrot”).
  • Move to the right, middle element (index 3, value “dragonfruit”).
  • No further movement, target not found in 3 comparisons.

âś… Free Response Questions

  1. Why is binary search more efficient for large data than linear search? Binary search is more efficient because it divides the search space in half with each comparison, leading to a time complexity of O(log n). In contrast, linear search examines each element one by one, resulting in O(n) time complexity. As the data grows, binary search performs significantly fewer comparisons.

  2. What happens if the list isn’t sorted and you try to use binary search? Binary search relies on the list being sorted, as it uses the divide-and-conquer approach. If the list isn’t sorted, the search will fail or yield incorrect results because the assumptions made by the algorithm about the relative ordering of elements are violated.

  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 streaming service search bar if the list of scores or results is sorted. Binary search allows for quick retrieval of information from large datasets, making it ideal for fast searches. However, the list must remain sorted for it to work properly.