interpolation-search-algorithm

Posted on Edited on Views:

插值查找算法

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
33
34
35
/**
 * @Author: Wizard
 * @Date: 2020/6/17 9:06
 */
public class insertSearch {
    /**
     * @param arr     数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 要查找的值
     * @return
     */
    public static int insertValue(int[] arr, int left, int right, int findVal) {
        System.out.println("插值查找次数...");

        //注意：findVal<arr[0]和findVal>arr[arr.length-1]必须需要
        //否则得到的mid可能越界
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }

        //求出mid,自适应
        int mid = left + (right - left) * (findVal - arr[left] / arr[right] - arr[left]);
        int midVal = arr[mid];
        if (findVal > midVal) {
            //应该向右递归
            return insertValue(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return insertValue(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
}