1. Which of the following is not an alternate name of exponential search?
a) Logarithmic search
b) Doubling search
c) Galloping search
d) Struzik search
Explanation: 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.
2. Which of the following is the most desirable condition for interpolation search?
a) array should be sorted
b) array should not be sorted but the values should be uniformly distributed
c) array should have a less than 64 elements
d) array should be sorted and the values should be uniformly distributed
Explanation: 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.
3. Interpolation search is a variation of?
a) Linear search
b) Binary search
c) Jump search
d) Exponential search
Explanation: 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.
4. Interpolation search performs better than binary search when?
a) array has uniformly distributed values but is not sorted
b) array is sorted and has uniform distribution of values
c) array is sorted but the values are not uniformly distributed
d) array is not sorted
Explanation: 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.
5. In which of the following case jump search performs better than interpolation search?
a) When array has uniformly distributed values but is not sorted
b) when array is sorted and has uniform distribution of values
c) when array is sorted but the values increases exponentially
d) when array is not sorted
Explanation: 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(n1/2). So in such a case jump search has a better performance.
6. What is the time complexity of interpolation search when the input array has uniformly distributed values and is sorted?
a) O(n)
b) O(log log n)
c) O(n log n)
d) O(log n)
Explanation: 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).
7. What is the auxiliary space requirement of interpolation search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Explanation: Interpolation search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).
8. What is the time complexity of exponential search when the input array is sorted but the values are not uniformly distributed?
a) O(n1/2)
b) O(log log n)
c) O(n)
d) O(log n)
Explanation: 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.
9. Which of the following searching algorithm is fastest when the input array is sorted and has uniformly distributed values?
a) jump search
b) exponential search
c) binary search
d) interpolation search
Explanation: 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.
10. Which of the following searching algorithm is fastest when the input array is sorted but has non uniformly distributed values?
a) jump search
b) linear search
c) binary search
d) interpolation search
Explanation: 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.
Design and Analysis of Algorithms
What's the Buzz about Interpolation Search?
Imagine you're at a library, searching for your favorite book. Instead of scanning every shelf methodically, wouldn't it be great if you could predict where it might be? That's the magic of Interpolation Search - it's like having a Sherlock Holmes for your data!
Cracking the Code: Interpolation Unveiled
Interpolation Search is a clever algorithm that goes beyond the traditional binary search. It doesn't just stick to the middle; it takes a sneak peek into the data distribution. It's like finding your way in a maze with a hint at every turn!
The Math Behind the Magic
Interpolation Search doesn't rely on luck; it's a blend of intuition and calculation. Picture this: if you're looking for a song in your playlist, you don't start from the first song, right? You jump ahead based on the title, and that's precisely what interpolation does!
Why Interpolation?
You might wonder, "Why choose Interpolation over the classic Binary Search?" Well, my friend, it's all about efficiency. When your data is uniformly distributed, Interpolation Search shines like a beacon, outpacing its binary cousin.
Conclusion: The Algorithmic Marvel
In the vast universe of algorithms, Interpolation Search stands out as a charming detective, making our search adventures a tad more thrilling. So, whether you're navigating a playlist or a massive dataset, consider letting Interpolation Search be your guide. Happy searching!