Past exam question: 2073 Bhadra (Regular), Q9
Open in the Padhaiko appQuestion
Explain a binary search with example. Consider a hash table of size 10. Using linear probing, insert the keys 62, 37, 36, 44, 67, 91, 82 and 107.
Solution
Binary Search with Example: Binary search searches a sorted array A[0..n-1] by comparing key with A[mid] where mid = (low + high) / 2, discarding half of the remaining elements at each step ( time). Example: Search 30 in [10, 20, 30, 40, 50]: low=0, high=4 -> mid=2 -> A[2]=30 (found in 1 probe).
Linear Probing Trace (, ):
- 62: slot 2.
- 37: slot 7.
- 36: slot 6.
- 44: slot 4.
- 67: (occupied) slot 8.
- 91: slot 1.
- 82: (occupied) slot 3.
- 107: (occupied),
8(occupied) slot 9.
Final Hash Table:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 91 | 62 | 82 | 44 | — | 36 | 37 | 67 | 107 |
Answer:
- Binary Search: Halves a sorted array in per search.
- Final Hash Table (slots
0..9):[—, 91, 62, 82, 44, —, 36, 37, 67, 107].