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

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

	while (lo <= hi) {
		mid = 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[5] = { 14, 26, 43, 72, 321 };
int index = Search(list, 5, 72);
								

Output

									index: 3