1. Introduction to interpolation search principle

The interpolation search algorithm is similar to binary search except that the interpolation search starts at the adaptive MID each time.

2. Convert the formula for mid index in the split search,

Low means left index left, high means right index right. Key is the same as findVal

3. Interpolation index

int mid = low + (high – low) * (key – arr[low]) / (arr[high] – arr[low]);

Corresponding to the previous code formula:

Int mid = left + (right — left) * (findVal — arr[left])/(arr[right] — arr[left])

4. Give examples

Find an array of algorithms 1-100

5. Precautions

  1. For the search table with large amount of data and uniform distribution of keywords, interpolation search is faster.

  2. This method is not necessarily better than half search when the distribution of keywords is not uniform

Case 6.

Interpolate an ordered array to find {1,8, 10, 89, 1000, 1234}, enter a number to see if it exists in the array, and find the subscript. If not, prompt “there is no number”.

	public static void main(String[] args) {
		
// int [] arr = new int[100];
// for(int i = 0; i < 100; i++) {
// arr[i] = i + 1;
/ /}
		
		int arr[] = { 1.8.10.89.1000.1000.1234 };
		
		int index = insertValueSearch(arr, 0, arr.length - 1.1234);
		//int index = binarySearch(arr, 0, arr.length, 1);
		System.out.println("index = " + index);
		
		//System.out.println(Arrays.toString(arr));
	}
	
	public static int binarySearch(int[] arr, int left, int right, int findVal) {
		System.out.println("Binary lookup called ~");
		// Left > right recurses the entire array, but is not found
		if (left > right) {
			return -1;
		}
		int mid = (left + right) / 2;
		int midVal = arr[mid];

		if (findVal > midVal) { // Recursive to the right
			return binarySearch(arr, mid + 1, right, findVal);
		} else if (findVal < midVal) { // Recurse to the left
			return binarySearch(arr, left, mid - 1, findVal);
		} else {

			returnmid; }}// Write the interpolation search algorithm
	// Note: The interpolation search algorithm also requires that the array is ordered
	/ * * * *@paramArray arr *@paramLeft Left index *@paramRight Index * on the right@paramFindVal finds the value *@returnReturns the corresponding subscript if found, or -1 */ if not found
	public static int insertValueSearch(int[] arr, int left, int right, int findVal) { 

		System.out.println("Interpolation search times ~~");
		
		// Note: findVal < arr[0] and findVal > arr[arr.length-1] must be required
		// Otherwise we may get the mid out of bounds
		if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
			return -1;
		}

		// Select mid ()
		int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
		int midVal = arr[mid];
		if (findVal > midVal) { // indicate that you should recurse to the right
			return insertValueSearch(arr, mid + 1, right, findVal);
		} else if (findVal < midVal) { // indicate a recursive search to the left
			return insertValueSearch(arr, left, mid - 1, findVal);
		} else {
			returnmid; }}Copy the code