PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q9

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

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 (, ):

Final Hash Table:

Index0123456789
Key—91628244—363767107
Answer:

All past exam questions for Data Structure and Algorithms