java语言实现二分查找、斐波那契查找、插值查询

java语言实现二分查找

/*
    二分查找法
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        int i = binarySearch1(arr,0,arr.length - 1, -1);
        System.out.println(i);
    }

    /**
     * @param value 查找的数值
     * @param arr 查找的数组
     * @return 返回查找到的下标  找不到返回-1
     */
    public static int binarySearch(int[] arr, int value){
        int left = 0;
        int right = arr.length - 1;
        int mid  = 0;
        while (left <= right){
            mid = (left + right) / 2;
            if(value > arr[mid]){
                left = mid + 1;
            }else if(value < arr[mid]){
                right = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    /**
     *
     * @param arr 查找的数组
     * @param left 数组的左边索引
     * @param right 数组的右边索引
     * @param value 查找的数值
     * @return  返回查找到的下标  找不到返回-1
     */
    public static int binarySearch1(int[] arr,int left,int right,int value){
        if(left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if(value < arr[mid]){
            //向左递归
            return binarySearch1(arr,left,mid-1,value);
        }else if(value > arr[mid]){
            return binarySearch1(arr,mid + 1,right,value);
        }else {
            return mid;
        }
    }
}

java语言实现斐波那契查找

package algorithm.search;

import java.util.Arrays;
/*
    斐波那契查找：
    黄金分割点：
    线段分为两部分，其中一部分与全长之比  =  另一部分与这部分之比
 */
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(Arrays.toString(fib(maxSize)));
        System.out.println(fibonacciSearch(arr,-10));

    }

    //创建一个斐波那契数列
    //[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
    public static int[] fib(int maxSize){
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr;
    }

    public static int fibonacciSearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;//5
        int mid = 0;
        //斐波那契数列的下标k
        int k = 0;
        //获取到斐波那契数列
        int[] f = fib(maxSize);
        //获取到斐波那契数列分割的下标
        while (high > f[k] - 1){
            k ++;//k = 5
        }
        //因为f[k]的长度可能会大于arr的长度,先用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        //然后用最大值进行填充
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];//{1,8,10,89,1000,1234,1234,1234}
        }
        while (low <= high){
            mid = low + f[k - 1] - 1;
            if(key < temp[mid]){
                high = mid - 1;
                k = k - 1;
            }else if(key >temp[mid]){
                low = mid + 1;
                k = k -2;
            }else {
                if(mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;
    }
}

java语言实现插值查询

import java.util.Arrays;

/*
    插值查询
    mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left])
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        System.out.println(insertValueSearch(arr,10));
        System.out.println("******************************");
        System.out.println(binarySearch(arr,10));
    }

    public static int binarySearch(int[] arr, int value){
        int left = 0;
        int right = arr.length - 1;
        int mid  = 0;
        int count = 0;
        while (left <= right){
            count ++;
            System.out.println("查找了" + count + "次...");
            mid = (left + right) / 2;
            if(value > arr[mid]){
                left = mid + 1;
            }else if(value < arr[mid]){
                right = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    public static int insertValueSearch(int[] arr,int value){
        int left = arr[0];
        int right = arr[arr.length - 1];
        if(value < left || value > right){
            return -1;
        }

        int mid = 0;
        int count = 0;
        while (left < right){
            count ++;
            System.out.println("查找了" + count + "次...");
            mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
            if(value < arr[mid]){
                right = mid - 1;
            }else if(value > arr[mid]){
                left = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}