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.

• C#
• VB.Net
• C
• C++
• PHP

									public static int Search(int[] list, int data)
{
	int lo = 0;
	int mid = -1;
	int hi = list.Length - 1;
	int 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

									int[] list = { 14, 26, 43, 72, 321 };
int index = Search(list, 72);
								

Output

									index: 3