Interpolation search

Best Case: log(log(n)

Average Case: log(log(n)

Worst Case: n

Interpolation search is an improvement of Bianry Search as it begins the search near the higher end of the array or lower end depending on the element it is searching for. Binary search on the other hand always searches in the middle of the array.

The following example implements a small function that uses interpolation search in an already sorted array.

C++/C example

   
//Function used to find the element in an sorted array
int InterSearch(int A[], int low, int high, int x) {

	//the array us sorted therefore the element will be within this range
	while (low <= high && x >= A[low] && x <= A[high])
	{
		//Get the current position using the formula to search nearer to high or nearer to low depending on element
		int pos = low + (((double)(high - low) / (A[high] - A[low])) * (x - A[low]));

		//if the element is found return it
		if (A[pos] == x)
		{
			return pos;
		}

		//If the element is larger than the higher part of the array
		if (A[pos] == x)
		{
			low = pos + 1;
		}
		//If the element is smaller than the lower part of the array
		else {
			high = pos - 1;
		}
	}
	return -1;
}

int main() {

	int A[] = { 0, 2, 5, 6, 7, 8, 9, 10, 11, 12 };
	int x = 9;
	int size = sizeof(A) / sizeof(A[0]);

	int location = InterSearch(A, 0, size - 1, x);

	if (location == -1) {
		std::cout << "Element not found" << std::endl;
	}
	else {
		std::cout << "Element found at: " << location << std::endl;
	}
	std::cin.get();
	return 0;
}
                

Summary

A more complex searching algorithm and works well with a uniform distributed data set. If you were searching for an element that was either very high in the data set or very low then this would be faster than binary search because it will search near the top or bottom.