算法 - Java实现二分、插值、斐波那契查找法

一、二分查找法

二分查找法，就是对一个有序数组进行拆分。找到这个数组的中间的那个数的值，将查找的这个数与其比较。这里是从小到大排序的，如果比这个中间值小，就在把中间值左边看成一个数组，在这个数组里继续二分查找，直到查到(或者查完全部也没查到).
如果比这个中间值大，就在把中间值右边看成一个数组，在这个数组里继续二分查找，直到查到(或者查完全部也没查到).

代码实现

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,6,7,8,9,10};
        int resIndex = binarySearch(nums, 5, 0, nums.length - 1);
        if (resIndex != -1){
            System.out.println("查找的数字的下标：" + resIndex);
        }else{
            System.out.println("该数字在数组中不存在！");
        }
    }

    /**
     * 二分查找法 - 在有序数组里查找一个数
     * @param nums 查找的数组
     * @param findVal 要查找的值
     * @param left 数组左端索引
     * @param right 数组右端索引
     * @return 查找到值的下标，没有查找到返回-1
     */
    public static int binarySearch(int[] nums, int findVal, int left, int right){
        if (left > right){   // 找遍整个数组，未发现该数
            return -1;
        }
        int mid = (left + right) / 2;  // 中间索引
        int midVal = nums[mid];        // 数组最中间的值

        if (findVal < midVal){  // 在右边查询
            return binarySearch(nums, findVal, left, mid - 1);
        }else if (findVal > midVal){ // 在左边查询
            return binarySearch(nums, findVal, mid + 1, right);
        }else{  // 找到了
            return mid;
        }
    }
}

二、插值查找法

插值查找算法类似于二分查找，也需要有序数组，不同的是插值查找每次从自适应mid处开始查找。
二分查找法中的求mid索引的公式为：

插值查找法中的求mid 索引的公式换成如下：

注：nums就是要查找的数组，left就只最左端，right就是最右端，findVal就是要查找的值

代码实现

public class InsertSearchDemo {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,6,7,8,9,10};
        int resIndex = insertSearch(nums, 5, 0, nums.length - 1);
        if (resIndex != -1){
            System.out.println("查找的数字的下标：" + resIndex);
        }else{
            System.out.println("该数字在数组中不存在！");
        }
    }

    /**
     * 插值查找法 - 在有序数组里查找一个数
     * @param nums 查找的数组
     * @param findVal 要查找的值
     * @param left 数组左端索引
     * @param right 数组右端索引
     * @return 查找到值的下标，没有查找到返回-1
     */
    public static int insertSearch(int[] nums, int findVal, int left, int right){
        /**
         * findVal < nums[0] 和 findVal > nums[nums.length - 1]条件必须要有，否则可能导致mid越界
         */
        if (left > right || findVal < nums[0] || findVal > nums[nums.length - 1]){   // 找遍整个数组，未发现该数
            return -1;
        }
        // 求出自适应mid
        int mid = left + (right - left) * (findVal - nums[left]) / (nums[right] - nums[left]);
        int midVal = nums[mid];

        if (findVal < midVal){  // 在右边查询
            return insertSearch(nums, findVal, left, mid - 1);
        }else if (findVal > midVal){ // 在左边查询
            return insertSearch(nums, findVal, mid + 1, right);
        }else{  // 找到了
            return mid;
        }
    }
}

三、斐波那契(黄金分割)查找法

黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其(比值)前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。

斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列）。数组依然得是有序数组。

对F(k-1)-1的理解

1、由斐波那契数列F[k]=F[k-1]+F[k-2]的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1。
该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
2、类似的，每一子段也可以用相同的方式分割
3、**但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。**这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

代码实现

public class FibonacciSearchDemo {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5,6,7,8,9,10};
        System.out.println("index=" + fibonacciSearch(nums,6));
    }

    /**
     * 斐波那契查找法
     * @param nums 查找的数组
     * @param findVal 要查找的值
     * @return 查找到值的下标，没有查找到返回-1
     */
    public static int fibonacciSearch(int[] nums, int findVal){
        int left = 0;
        int right = nums.length - 1;
        int k = 0;      // 表示斐波那契分割数值的下标
        int mid = 0;    // 存放mid值
        int[] f = createFibSeq(20);   // 斐波那契数列，这里就使用f命名，符合公式里的F(n)

        // 找到斐波那契分割数值的下标
        while(right > f[k] - 1){
            k++;
        }

        // 因为f[k]的值可能大于nums的长度，因此需要构造一个新的数组指向temp
        // copyOf方法不足的地方会用0填充
        int[] temp = Arrays.copyOf(nums,f[k]);

        // 实际上应该用数组最后一个数来填充
        for (int i = right + 1; i < temp.length; i++){
            temp[i] = nums[right];
        }

        while (left <= right){
            mid = left + f[k - 1] - 1;
            if (findVal < temp[mid]){
                // 向前找,确定向前找之后，那么right就会变成mid - 1，后半截不用管了
                right = mid - 1;
                /**
                 * 因为 f[k] = f[k - 1] + f[k - 2],即全部元素 = 前面元素 + 后面元素
                 * 这里是往前找，即前面有f[k - 1],根据公式变换（实际就是把k-1看做一个整体）
                 * f[k - 1] = f[k - 1 - 1] + f[k - 1 - 2]
                 * ==> mid = f[k - 1 - 1] - 1
                 */
                k--;
            }else if (findVal > temp[mid]){
                // 向后找,确定向后找之后，那么left就会变成mid + 1
                left = mid + 1;
                /**
                 * 同样的道理
                 * f[k - 2] = f[k - 2 - 1] + f[k -2 - 2]，把k-2看做一个整体
                 * ==> mid = f[k - 2 - 1] - 1
                 */
                k-=2;
            }else{  // 找到了
                // 确定返回的下标
                if (mid <= right){
                    return mid;
                }else{
                    return right;
                }
            }
        }
        return -1;

    }

    /**
     * 创建一个斐波那契数列，公式： F(n)=F(n - 1)+F(n - 2)
     * @param length 斐波那契数列的长度，这个值越大，后一项与前一项的比值越来越逼近黄金分割0.618
     * @return 斐波那契数列
     */
    public static int[] createFibSeq(int length){
        int[] fibonacciSeq = new int[length];
        fibonacciSeq[0] = 1;
        fibonacciSeq[1] = 1;
        for (int i = 2; i < length; i++){
            //  公式：F(n)=F(n - 1)+F(n - 2)
            fibonacciSeq[i] = fibonacciSeq[i - 1] + fibonacciSeq[i - 2];
        }
        return fibonacciSeq;
    }
}