Interpolation Search

Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in sorted and equally distributed form.

									function Search($list, $data) {
	$lo = 0;
	$mid = -1;
	$hi = count($list) - 1;
	$index = -1;

	while ($lo <= $hi) {
		$mid = (int)($lo + (((double)($hi - $lo) / ($list[$hi] - $list[$lo])) * ($data - $list[$lo])));

		if ($list[$mid] == $data) {
			$index = $mid;
			break;
		}
		else {
			if ($list[$mid] < $data)
				$lo = $mid + 1;
			else
				$hi = $mid - 1;
		}
	}

	return $index;
}

Example

									$list = array(14, 26, 43, 72, 321);
$index = Search($list, 72);

Output

									index: 3