欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java数据结构之插值查找和斐波那契查找

程序员文章站 2022-07-12 09:51:41
...

插值查找:

二分查找在确定中间值的位置的时候,使用的公式为:
    mid = (right + left) / 2
    此公式可以转换为:mid = left + (right - left) / 2
    上面的公式中 1/2 我们可以进行优化:
    设要查找的值为 targetVal
    (targetVal - a[left]) / (a[right] - a[left]) * (right - left)
    此公shi能够比较快速的定位到 targetVal倾向于偏到哪一个方向
    因此有 mid = left + (right - left) * (targetVal - a[left]) / (a[right] - a[left])
    优于 mid = left + (right - left) / 2,同样插值查找也需要数组是有序的,在a中的值分布不均匀,跳跃性很大的
    情况下,插值查找不一定比二分查找好

 

代码:

public class InsertValueSearch {
    public static void main(String[] args) {
        int len = 100;
        int[] a = new int[len];
        for ( int i = 0; i < len; i++) {
            a[i] = i;
        }
        int findVal = 45;
        int pos = insertSearch(a, 0, a.length-1, findVal);
        System.out.printf("要查找的值为:%d, pos:%d\n", findVal, pos);
    }

    //找到返回对应的下标,找不到返回-1
    public static int insertSearch(int a[], int left, int right, int findVal) {
        System.out.println("Hello~~");
       //插值查找 findVal < a[left] || a[right] < findVal 必须有
        if (left > right || findVal < a[left] || a[right] < findVal) {

            return -1;
        }
        int mid = left +  (right - left) * (findVal - a[left]) / (a[right] - a[left]);
        int midVal = a[mid];

        if (findVal > midVal) {
            return insertSearch(a, mid+1, right, findVal);
        } else if (findVal < midVal) {
            return insertSearch(a, left, mid-1, findVal);
        } else {
            return mid;
        }

    }

}

斐波那契查找

   0.618让人看了很舒服
   在二分查找确定 1/2的时候,我们可以确定0.618
   斐波那契数前一个数比上后一个数的比例接近于0.618

代码:

public class FibonacciSearch {
    public static void main(String[] args) {
        int len = 100;
        int[] a = new int[len];
        for ( int i = 0; i < len; i++) {
            a[i] = i;
        }
        int[] a1 = {1, 8, 10,89,1000,1234};
        int findVal = 45;
        int i = fibonacciSearch(a1, findVal);

    }

    public static int fibonacciSearch(int a[], int findVal) {
        int low = 0;
        int high = a.length - 1;
        int k = 0;
        int mid = 0; //
        int f[] = fib(20);

        //获取到斐波那契数值的下标
        while (high > f[k] - 1) {
            k++;
        }
        //因为f[k] 值可能大于数组的长度,因此使用Arrays类构造一个新的数组,并指向a[]
        //不足的部分使用0填充
        int[] tmp = Arrays.copyOf(a, f[k]);
        //需要使用a数组最后的数填充tmp
        for (int i =  high+1; i < tmp.length; i++) {
            tmp[i] = a[high];
        }

        //循环查找,直到找到目标数
        while (low <= high) {
            mid = low + f[k-1] -1;
            if (findVal < tmp[mid]) { //向数组前面查找
                high = mid-1;
                k--; //全部元素 = 前面的元素 + 后面的元素。 f[k] = f[k-1] + f[k-2]
                //前面有f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3],即在f[k-1]的前面继续查找
            } else if (findVal > tmp[mid]) { //想数组后面查找
                low = mid+1;
                k -= 2; //全部元素 = 前面元素 + 后面元素
                //f[k] = f[k-1]+ f[k-2], 因为f
            } else {
                //需要确定返回的是哪一个坐标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }


            }
        }

        return  -1;
    }

    //非递归方法获取斐波那契数列
    public static int[] fib(int maxSize) {
        int[] f = new int[maxSize];
        if (maxSize < 2) {
            f = new int[2];
        }

        f[0]= 1;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = f[i-1]+f[i-2];
        }

        return f;
    }
}