Data Structure And Algorithm : Practice Questions and Answers

When the element being searched is lower than the value at the calculated position then in that case we update high and low remains unaltered. Updated value of high is high = pos - 1.

When the element being searched is greater than the value at the calculated position then in that case we update low and high remains unaltered. Updated value of low is low = pos + 1.

For calculating the position after each iteration in interpolation search we use the formula low + ((x - A[low]) * (high - low)) / (A[high] - A[low]). Then the value at the calculated position is compared with the element being searched.

The worst case time complexity of interpolation search and exponential search are O(n) and O(log n) respectively. So exponential search is better when the worst case scenario is considered.

Interpolation search has an auxiliary space complexity of O(1). So it qualifies as an in place algorithm.

Out of the given options linear search is the only searching algorithm which can be applied to arrays which are not sorted. It has a time complexity of O(n) in the worst case.

Interpolation search has a time complexity of O(n) when the array does not have uniformly distributed values. So in such a case binary search has the least time complexity out of the given options.

Interpolation search has a time complexity of O( log log n) when the array is sorted and has uniformly distributed values. It has the least time complexity out of the given options for such a case.

When an array has non uniformly distributed values then in that case the algorithm of interpolation search fails to work efficiently. As a result, it has a time complexity of O(n) in such a case.

Interpolation search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).

Interpolation search goes to different positions in the array depending on the value being searched. It is an improvement over binary search and has a time complexity of O(log log n).

In case of non uniform distribution of values the time complexity of interpolation search is O(n) whereas the average time complexity of jump search is O(n^{1/2}). So in such a case jump search has a better performance.

Interpolation search is an improvement over a binary search for the case when array is sorted and has uniformly distributed values. Binary search performs better when the values are not distributed uniformly.

Interpolation search is a variation of binary search which gives the best result when the array has uniformly distributed values. Interpolation search goes to different positions depending on the value being searched whereas binary search always goes to the middle element.

Desirable condition for interpolation search is that the array should be sorted and the values should be uniformly distributed. The algorithm would fail to give the correct result if array is not sorted.

Logarithmic search is not an alternate name of the exponential search. Some alternate names of exponential search are Doubling search, Galloping search and Struzik search.

Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being searched is present near the starting point of the array.

Exponential search first finds the range where binary search needs to be applied. So when the element is present near the starting point of the array then exponential search performs better than standard binary search.

The worst case time complexity of jump search and exponential searches are O(n1/2) and O(log n) respectively. So exponential search is better in terms of time complexity.

Best case of the exponential search will be when the first element of the array is the element that is being searched. In this case, only one comparison will be required. Thus it will have a time complexity of O(1).