HOMEWORK HACKS
Hack pt A
- 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
answer = 010101
- 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
answer = 11001
3. 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
answer = 0010011
Hack pt B
- 101010
2^5 = 32
1 x 32 = 32
0 x 16 = 0
1 x 8 = 8
0 x 4 = 0
1 x 2 = 2
0 x 1 = 0
Total = 42
- 10011
2^4 = 16
1 x 16 = 16
0 x 8 = 0
0 x 4 = 0
1 x 2 = 2
1 x 1 = 1
**Total = 19
- 110011
2^5 = 32
1 x 32 = 32
1 x 16 = 16
0 x 8 = 0
0 x 4 = 0
1 x 2 = 2
1 x 1 = 1
Total = 51
Hakc pt C
LIST = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
- Search for 18
Low = 0, High = 10, Mid = (0+10)//2 = 5
List[5] = 18 –> Found!
Comparisons made: 1
Found? Yes
- Search for 33
Low = 0, High = 10, Mid = (0+10)//2 = 5
List[5] = 18 –> search right
List [7] = 24
List [9] = 30
List [10] = 33 –> Found!
Comparisons made: 4
Found? Yes
- Search for 5
Low = 0, High = 10, Mid = (0+10)//2 = 5
List[5] = 18 –> search left
List [3] = 12
List [1] = 6
List [0] = 3 –> Not found search ended :(
Comparisons made: 6
Found? No
Hack pt D
LIST = [“apple”, “banana”, “carrot”, “dragonfruit”, “fig”, “grape”, “kiwi”, “mango”, “orange”, “peach”, “watermelon”]
- Search for mango Step 1:
Low = 0, High = 10 → Mid = 5
List[5] = “grape” → “mango” > “grape” → search right
Step 2:
Low = 6, High = 10 → Mid = 8
List[8] = “orange” → “mango” < “orange” → search left
Step 3: Low = 6, High = 7 → Mid = 6
List[6] = “kiwi” → “mango” > “kiwi” → search right
Step 4: Low = 7, High = 7 → Mid = 7
List[7] = “mango” → Found!
Comparisons made: 4
Found? Yes
- Search for Carrot
Step 1:
Low = 0, High = 10 → Mid = 5
List[5] = “grape” → “carrot” < “grape” → search left
Step 2: Low = 0, High = 4 → Mid = 2
List[2] = “carrot” → Found!
Comparisons made: 2
Found? Yes
- Search for lemon
Step 1:
Low = 0, High = 10 → Mid = 5
List[5] = “grape” → “lemon” > “grape” → search right
Step 2:
Low = 6, High = 10 → Mid = 8
List[8] = “orange” → “lemon” < “orange” → search left
Step 3:
Low = 6, High = 7 → Mid = 6
List[6] = “kiwi” → “lemon” > “kiwi” → search right
Step 4:
Low = 7, High = 7 → Mid = 7
List[7] = “mango” → “lemon” < “mango” → search left
Now Low = 7, High = 6 → search ends.
Comparisons made: 4
Found? No
Free response questions:
- Why is binary search more efficient for large data than linear search?
Binary search cuts the search space in half with each step, making it much faster to find numbers/items compared to linear search, which checks each item one by one. This difference becomes huge as the list grows larger.
- What happens if the list isn’t sorted and you try to use binary search?
Binary search won’t work correctly in an unsorted list because it depends on knowing which side of the middle the target might be. If the list isn’t sorted, it might skip over the correct value or give wrong results, makeing it ineffective in unsorted lists.
- Could you use binary search in a video game leaderboard or streaming service search bar? Why or why not?
Yes, if the leaderboard or search index is sorted, binary search can quickly find players or titles. However, for more flexible searches like partial matches or recommendations, other methods may be better.