插值查找

分析

相当于对二分查找的一种优化，让mid指针更加精确

image-20210409173339371

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package 算法;

public class 插值查找 {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i <100 ; i++) {
           arr[i] = i+1;
        }
        int index = insertValueSearch(arr, 0, arr.length-1, 99999);
        System.out.println(index);
    }
    public static int insertValueSearch(int[] arr,int left,int right,int num){
        if(num<arr[left]||num>arr[right]){
            return -1;
        }
        int l =left;
        int r = right;
        int mid = l + (r-l)*(num-arr[l])/(arr[r]-arr[l]);
        while (l<=r){
            if(arr[mid]==num){
                return mid;
            }
            if(arr[mid]>num){
                r = mid-1;
            }else{
                l = mid+1;
            }
            mid = l + (r-l)*(num-arr[l])/(arr[r]-arr[l]);
        }
        return -1;
    }
}