## Overview

I wrote about binary search in my previous post, which is indeed one very fast searching algorithm, but in some cases we can achieve even faster results. Such an algorithm is the “interpolation search” – perhaps the most interesting of all searching algorithms. However we shouldn’t forget that the data must follow some limitations. In first place the array must be sorted. Also we must know the bounds of the interval.

Why is that? Well, this algorithm tries to follow the way we search a name in a phone book, or a word in the dictionary. We, humans, know in advance that in case the name we’re searching starts with a “B”, like “Bond” for instance, we should start searching near the beginning of the phone book. Thus if we’re searching the word “algorithm” in the dictionary, you know that it should be placed somewhere at the beginning. This is because we know the order of the letters, we know the interval (a-z), and somehow we intuitively know that the words are dispersed equally. These facts are enough to realize that the binary search can be a bad choice. Indeed the binary search algorithm divides the list in two equal sub-lists, which is useless if we know in advance that the searched item is somewhere in the beginning or the end of the list. Yes, we can use also jump search if the item is at the beginning, but not if it is at the end, in that case this algorithm is not so effective.

So the interpolation search is based on some simple facts. The binary search divides the interval on two equal sub-lists, as shown on the image bellow.

What will happen if we don’t use the constant ½, but another more accurate constant “C”, that can lead us closer to the searched item.

The question is how to find this value? Well, we know bounds of the interval and looking closer to the image above we can define the following formula.

C = (x-L)/(R-L) |

Now we can be sure that we’re closer to the searched value.

## Implementation

Here’s an implementation of interpolation search in PHP.

$list = array(201, 209, 232, 233, 332, 399, 400); $x = 332; function interpolation_search($list, $x) { $l = 0; $r = count($list) - 1; while ($l <= $r) { if ($list[$l] == $list[$r]) { if ($list[$l] == $x) { return $l; } else { // not found return -1; } } $k = ($x - $list[$l])/($list[$r] - $list[$l]); // not found if ($k < 0 || $k > 1) { return -1; } $mid = round($l + $k*($r - $l)); if ($x < $list[$mid]) { $r = $mid - 1; } else if ($x > $list[$mid]) { $l = $mid + 1; } else { // success! return $mid; } // not found return -1; } } echo interpolation_search($list, $x); |

## Complexity

The complexity of this algorithm is log_{2}(log_{2}(n)) + 1. While I wont cover its proof, I’ll say that this is very slowly growing function as you can see on the following chart.

Indeed when the values are equally dispersed into the interval this search algorithm can be extremely useful – way faster than the binary search. As you can see log_{2}(log_{2}(100 M)) ≈ 4.73 !!!

## Application

As I said already this algorithm is extremely interesting and very appropriate in many use cases. Here’s an example where interpolation search can be used. Let’s say there’s an array with user data, sorted by their year of birth. We know in advance that all users are born in the 80’s. In this case sequential or even binary search can be slower than interpolation search.

$list = array( 0 => array('year' => 1980, 'name' => 'John Smith', 'username' => 'John'), 1 => array('year' => 1980, ...), ... 10394 => array('year' => 1981, 'name' => 'Tomas M.', ...), ... 348489 => array('year' => '1985', 'name' => 'James Bond', ...), ... 2808008 => array('year' => '1990', 'name' => 'W.A. Mozart', ...) ); |

Now if we search for somebody born in 1981 a good approach is to use interpolation search.

Hi, just a note – The interpolation search algorithm is O(log(log n)) only when the input is uniformly distributed.

In the worst case scenario the algorithm can cost up to O(n).

You should be careful when you use the word “complexity”. It usually means “worst case” but not in this case.

To be more precise, interpolation search is O(n) as correctly noted by Ehud, but

on averageit behaves like O(log log n). This strongly depends on the distribution of your input, so interpolation is not always a better choice as O(n) is very slow.On the other hand, binary search is always O(log n), whatever the input.

Although what you’re writing about is quite technical (probably an understatement), I found your description and diagrams quite easy to follow.

About me: I’m a blogger for http://www.itrentals.com

plz give aproof for its time complexity

really nice 🙂 better dan wikipedia 😉 i love da diagrammatic description dat u gave

Many thanks for making the effort to natter regarding this, I stroke starkly about this and enjoy learning a vast covenant more proceeding this matter. Condition viable, as you gain expertise, would you mind updating your webpage with a vast deal further details? It’s fantastically practical for me.

Very easy to understand. Although not enough deep drilling but good for first time reader. Graphical representations are always better than text.

interpolation search…that’s it..?i thought it was something that couldn’t be understood by a first time reader.but it felt quite simple. Thank you…

Good examlpe but if the result not found you need to keep running the loop but in the example you return -1 how loop continues to next stage.