I've been working on web based projects built mainly with PHP and JavaScript, where I mostly use Zend Framework and jQuery. I am interested in any webpage optimizations techniques - for a faster web! Stoimen is a DZone MVB and is not an employee of DZone and has posted 96 posts at DZone. You can read more from them at their website. View Full User Profile

Algorithm of the Week: Interpolation Search

01.03.2012
| 11798 views |
  • submit to reddit

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.

Binary search basic approach

The binary search algorithm divides the list in two equal sub-lists!

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.

Interpolation search

The interpolation search algorithm tries to improve the binary search!

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 log2(log2(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.

log(n) compared to log(log(n))

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 log2(log2(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.

 

Source: http://www.stoimen.com/blog/2012/01/02/computer-algorithms-interpolation-search/

 

Published at DZone with permission of Stoimen Popov, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Kathy John replied on Thu, 2012/02/23 - 10:47am

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 average it 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.

Caravan Johns replied on Fri, 2012/04/20 - 4:33am

line 38

 "return -1;"

should be outside of while loop

 

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.