Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
When should I used interpolation search instead of binary search?
For example, I have a sorted dataset, in what situations would I use binary search to find an item in this dataset or in which situation should I used interpolation search?
What properties of the dataset would be the determining factor?
Obviously, to do an interpolation search, you need some type of key for which more than ordering is known -- you have to be able to do computations on the keys to estimate a likely distance, not just compare keys to determine which is greater or lesser.
As far as properties of the dataset go, it mostly comes to one property: a likelihood that the keys are reasonably evenly (or at least predictably) distributed throughout the range of possibilities. Without that, an interpolation search can actually be slower than a binary search.
For example, consider a data set with strings of lower-case letters as keys. Let's assume you have a key that starts with "x". An interpolation search will clearly indicate that you should start searching very close to the end of the set. If, however, most of your keys actually start with 'z', and almost none with anything from 'a' though 'y', the one you're searching for may actually be very close to the beginning of the set instead. It can/may take a considerable number of iterations before the search gets close to the beginning where the string starting with 'w' reside. Each iteration would remove only ~10% of the data set from consideration, so it would take several iterations before it got close to the beginning where the keys starting with 'w' actually reside.
By contrast, a binary search would start at the middle, get to the one-quarter mark at the second iteration, one-eighth mark on the third, and so on. Its performance would be nearly unaffected by the skew in the keys. Each iterations would remove half the data set from consideration, just as if the keys were evenly distributed.
I hasten to add, however, that it really does take quite a skewed distribution to make an interpolation search noticeably worse than a binary search. It can, for example, perform quite well even in the presence of a fair amount of localized clustering.
I should also mention that an interpolation search does not necessarily need to use linear interpolation. For example, if your keys are known to follow some non-linear distribution (e.g., a bell-curve), it becomes fairly easy to take that into account in the interpolation function to get results little different from having an even distribution.
a, however, would hurt performance dramatically.
Nov 14, 2011 at 20:19
I'd likely think the question is how easily can you come up with an interpolation function that actually does better than binary search.
From Wikipedia on Interpolation Search:
Using big-O notation, the performance of the interpolation algorithm on a data set of size N is O(N); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log N).
Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe. It can be useful for locating a record in a large sorted file on disk, where each probe involves a disk seek and is much slower than the interpolation arithmetic.
Index structures like B-trees also reduce the number of disk accesses, and are more often used to index on-disk data in part because they can index many types of data and can be updated online. Still, interpolation search may be useful when one is forced to search certain sorted but unindexed on-disk datasets.
Binary search and interpolation search are both considered as linear search methods.
They both expect the list being searched to be sorted on the column refered to as the key. This is very important.
Binary search works for strings or numbers as long as they are stored in sorted order. The primary idea behind Binary search is that it is based on examining the middle element. Interpolation search is a variant. Instead of using the exact middle element it guesses where the next element to compare with passed value is. See the reference provided by JB King answer or the one below in this answer for details on how the interpolation search algorithm calculates the next key value.
"Interpolation search works only on numerical elements arranged in sorted arrays order with uniform distribution (that is, the interval between any to successive elements are roughly constant" (quote from reference below P 737, also a performance comparison between different linear search methods are included).
