java实现插值查找和斐波那契查找算法

插值查找

package com.csw.search;

import java.util.Arrays;

/**
 * @Auther: 行路
 * @Date: Created on 2020/4/24 16:47 星期五
 * @Description: com.csw.search 插值查找
 * @version: 1.0
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr=new int[100];
        for(int i=0;i<100;i++){
            arr[i]=i+1;
        }
        int i = insertValueSearch(arr, 0, arr.length - 1, 33);
        System.out.println("查找次数:"+count+"，查找到的下标为:"+i);
    }

    /**
     * 插值查找算法
     * 要求数组是有序的
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return //如果找到,就返回对应的值,如果没有找到,返回-1
     */
    public static int count=0;
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        ++count;
        //注意这两个条件必须有,否则会得到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 insertValueSearch(arr,mid+1,right,findVal);                    //说明向右递归查找
        }else if(findVal<midVal){
            return insertValueSearch(arr,left,mid-1,findVal);
        }else{
            return mid;
        }
    }
}

斐波那契查找

package com.csw.search;

import java.util.Arrays;

/**
 * @Auther: 行路
 * @Date: Created on 2020/4/23 23:19 星期二
 * @Description: com.csw.search 斐波那契查找算法
 * @version: 1.0
 */
public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(fibSearch(arr,1234));
    }

    //mid=low+F(k-1)+1,后面需要使用斐波那契数列,因此我们需要先获取到一个斐波那契数列
    //非递归的方式得到斐波那契数列
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 使用非递归
     * 编写斐波那契查找算法
     *
     * @param a   数组
     * @param key 我们需要查找的关键码
     * @return 返回对应的小标, 如果没有-1
     */
    public static int fibSearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        int k = 0;  //表示斐波那契分割数值对应下标
        int mid = 0;  //存放mid值
        int[] f = fib();  //获取斐波那契数列
        //获取到斐波那契分割值的小标
        while (high > f[k] - 1) {
            k++;
        }
        //因为f[k]值大于a的长度,因此许Arrays类,构造一个新的数组,并指向a[]
        int[] temp = Arrays.copyOf(a, f[k]);
        //实际上需要使用a数组最后的数填充temp
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        //使用while循环来循环处理,找到我们的数key
        while (low <= high) {
            //只要这个添加满足,就可以一直找
            mid = low + f[k - 1] - 1;
            if(key<temp[mid]){
                //说明我们应该向数组的前面查找
                high=mid-1;
                //1.全部元素=前面的元素+后边的元素
                //2.f[k]=f[k-1]+h[k-2]
                //因为前面有f[k-1]个元素,所以可以继续拆分f[k-1]=f[k-2]+f[k-3]
                //即f[k-1]的前面继续查找k--;
                //即下次循环mid=f[k-1-1]-1;
                k--;
            }else if(key>temp[mid]){ //说明向数组 的后面查找
                low=mid+1;
                //为什么是k-=2,1.全部元素=前面的元素+后边的元素
                //因为后面我们有f[k-2]个元素所以我们可以继续拆分
                //mid=f[k-1-2]-1
                k-=2;
            }else{
                //需要确定返回的是那个下标
                if(mid<=high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}