1 Search the key value 128 from the following record 209 24

1. Search the key value 128 from the following record 209, 24, 17, 106, 245, 128, 216, 156 by using the following two different search techniques, respectively,

a) Sequential search.

b) Binary.

Show the exact running time you may need. The details of each searching step should be included.

2. For binary search, verify why the running time, in average, is O(log(n))?

3. Assume that you have a seven-slot hash table (the slots are numbered 0 through 6). Show final hash table that would result if you used the hash function h(k)=k mod(7) and linear probing on this list of numbers: 3, 12, 9, 2. After inserting the key with value 2, list for each empty slot the probability that it will be next one filled.

Solution

Given list: 209, 24, 17, 106, 245, 128, 216, 156.

Sequential Search: Here starting from the first element, we keep searching for an element sequentially, till either the element is found, or the list exhausts.

So, the comparisons go like this:

128 == 209: False.

128 == 24: False.

128 == 17: False.

128 == 106: False.

128 == 245: False.

128 == 128: True. Stop. Therefore, to search for 128, the total number of comparisons required in this case is: 6.

BinarySearch: Here everything using the index values, the mid value is calculated. If the element is
at index mid, stop searching, if element at mid is greater than search key, search only in the left
side list, else search only in the right side list.
The prerequisite is that the list should be sorted. So, after sorting, the list is:
17, 24, 106, 128, 156, 209, 216, 245.
So, initially, low = 0, and high = 7.
mid = (0 + 7) / 2 = 3.
128 == 128. True. Stop. Therefore, to search for 128, the total number of comparisons required in this case is: 1.

2. For binary search, verify why the running time, in average, is O(log(n))?

In binary search, every time the list size is halved. Either the left half or the right half. Therefore, the total number of comparisons is: log₂ n.

In the given example, as n value is 8. The maximum number of comparisons required to search for any element in the list is: 3.