Binary Search Algorithm #12
Description
Binary Search
What is Binary?
Binary is a 2-number system made of only 0 and 1.
- Bit: 1 binary digit (either 0 or 1)
- Byte: 8 bits → can represent up to 256 values
Decimal to Binary
To convert decimal to binary, divide the number by 2 and keep track of the remainders. Then, read the remainders from bottom to top.
Binary Search: An Overview
Binary search is a highly efficient algorithm that uses the "divide and conquer" method to find an item in a sorted list.
- Much faster than linear search.
- Used in systems like search engines, which index and filter content using binary logic.
Homework Hacks
Part A: Decimal to Binary Conversion
42 in binary:
42 / 2 = 21 R0
21 / 2 = 10 R1
10 / 2 = 5 R0
5 / 2 = 2 R1
2 / 2 = 1 R0
1 / 2 = 0 R1
→ 42 = 101010
19 in binary:
19 / 2 = 9 R1
9 / 2 = 4 R1
4 / 2 = 2 R0
2 / 2 = 1 R0
1 / 2 = 0 R1
→ 19 = 10011
100 in binary:
100 / 2 = 50 R0
50 / 2 = 25 R0
25 / 2 = 12 R1
12 / 2 = 6 R0
6 / 2 = 3 R0
3 / 2 = 1 R1
1 / 2 = 0 R1
→ 100 = 1100100
Part B: Binary to Decimal Conversion
We convert binary to decimal by adding powers of 2 for every 1 in the binary number, starting from the right (2⁰).
101010 = 42
- 2⁵ (32) + 2³ (8) + 2¹ (2) = 42
- Ignore positions with
0.
10011 = 19
- 2⁴ (16) + 2¹ (2) + 2⁰ (1) = 19
110011 = 51
- 2⁵ (32) + 2⁴ (16) + 2¹ (2) + 2⁰ (1) = 51
Part C: Binary Search Table (Numbers)
| Target | Step | Low | High | Mid Index | Mid Value | Comparison Result |
|---|---|---|---|---|---|---|
| 18 | 1 | 0 | 10 | 5 | 18 | Found |
| 33 | 1 | 0 | 10 | 5 | 18 | 33 > 18 → Right half |
| 2 | 6 | 10 | 8 | 27 | 33 > 27 → Right half | |
| 3 | 9 | 10 | 9 | 30 | 33 > 30 → Right half | |
| 4 | 10 | 10 | 10 | 33 | Found | |
| 5 | 1 | 0 | 10 | 5 | 18 | 5 < 18 → Left half |
| 2 | 0 | 4 | 2 | 9 | 5 < 9 → Left half | |
| 3 | 0 | 1 | 0 | 3 | 5 > 3 → Right half | |
| 4 | 1 | 1 | 1 | 6 | 5 < 6 → Left half | |
| 5 | 1 | 0 | - | - | Not found |
- All targets were found except for 5.
- The algorithm stops when
low > high.
Part D: Binary Search Table (Words)
| Target | Step | Low | High | Mid Index | Mid Value | Comparison Result |
|---|---|---|---|---|---|---|
| mango | 1 | 0 | 10 | 5 | grape | "mango" > "grape" |
| 2 | 6 | 10 | 8 | orange | "mango" < "orange" | |
| 3 | 6 | 7 | 6 | kiwi | "mango" > "kiwi" | |
| 4 | 7 | 7 | 7 | mango | Found | |
| carrot | 1 | 0 | 10 | 5 | grape | "carrot" < "grape" |
| 2 | 0 | 4 | 2 | carrot | Found | |
| lemon | 1 | 0 | 10 | 5 | grape | "lemon" > "grape" |
| 2 | 6 | 10 | 8 | orange | "lemon" < "orange" | |
| 3 | 6 | 7 | 6 | kiwi | "lemon" > "kiwi" | |
| 4 | 7 | 7 | 7 | mango | "lemon" < "mango" | |
| 5 | 7 | 6 | - | - | Not found |
- The translation from index numbers to words added a small complexity.
- "lemon" was not found.
FRQ Response
Why is binary search more efficient for large data than linear search?
Binary search is much more efficient because it cuts the data in half with every step. This is like opening a dictionary to the middle and deciding to look left or right, instead of reading every word from the start like in linear search. Less time, fewer steps.
What happens if the list isn’t sorted and you try to use binary search?
Binary search won’t work on unsorted data. It relies on order to know which half to ignore. Without sorting, you might skip over the correct answer or get a completely wrong result.
Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?
- Yes for a video game leaderboard — data like scores and ranks are always sorted, making binary search perfect.
- No for a streaming service search bar — results are personalized, trending, or filtered by genre, so they're not sorted in a strict way. Linear search or more advanced search algorithms are better for this case.