Interpolation lookup (two methods)

One 、 What is interpolation lookup

（1） Interpolation search algorithm is similar to binary search , The difference is that the interpolation lookup starts from The adaptive mid It's about Start looking for .

（2） Binary search mid The value is left and right The sum of the subscripts of the indicated sequence 1/2 namely mid = （left+right）/ 2.

（3） And interpolation search mid The value is calculated by formula , It is obvious from the formula mid The value of is not the middle position of the left and right indexes like dichotomy .

（4） Interpolation search formula ;3、int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;low Indicates the index on the left left,high Indicates the index on the right right. key Is the value you need to find .

Two 、 Features of interpolation search

（1） The search sequence must be ordered

（2） about Large amount of data And keywords Evenly distributed For the ordered sequence of , Interpolation search is faster .

（3） about Unevenly distributed For the ordered sequence of , This algorithm is not necessarily better than binary search .

3、 ... and 、 Code implementation

（1） Method 1 ： recursive

public class InterpolationSearch {

	public static void main(String[] args) {
		int [] arr= {1,3,9,12,14,17,24,28,29};
		int low = 0;
		int high = arr.length-1;
		int index = interpolationSearch(arr,low,high,17);
		System.out.print(" Element found 17 The location of the for ："+index);
	}
	public static int interpolationSearch(int[] arr, int low, int high, int key) {
       
        if (low > high) {
            return -1;
        }
        int mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
        if (mid < low || mid > high) {
            return -1;
        }
        if (arr[mid] == key) {
            return mid;
        } else if (key < arr[mid] ) {
            return interpolationSearch(arr,low,mid - 1,key);
        } else {
            return interpolationSearch(arr,mid + 1, high,key);
        }
    }

}

Running results ：

（2） Method 2 ： iteration

public class InterpolationSearch {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 9, 12, 14, 17, 24, 28, 29 };
		int index = insertvaluesearch(arr, 17);
		System.out.print(" Element found 17 The location of the for ：" + index);
	}

	public static int insertvaluesearch(int arr[], int key) {
		int low = 0;
		int high = arr.length - 1;
		while (low <= high) {
			int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
			if (arr[mid] == key) {
				return mid;
			}
			if (arr[mid] < key) {
				low = mid + 1;
			}
			if (arr[mid] > key) {
				high = mid - 1;
			}
		}
		return -1;
	}

}

  Running results ：