在Java中，常用的查找算法有以下四种：

• 顺序查找；
• 二分查找；
• 插值查找；
• 斐波那契查找；

---

欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。

---

一、顺序查找

顺序查找非常简单，就是遍历数组，找到了就返回元素下标，代码如下：

public static int find(int[] arr, int targetNum){
     if (arr == null) {
          return -1;
     }
     for (int i = 0; i < arr.length; i++) {
         if (arr[i] == targetNum){
             return i;
         }
     }
     return -1;
}

二、二分查找

二分查找又叫折半查找，首先二分查找的数列是要有序的，如果无序就不能用二分查找。

1. 二分查找思路：

• 首先确定该数组的中间下标，`mid = (left + right) / 2；
• 然后让arr[mid]和要和查找的元素比较，如果要查找的元素更大，说明应该向右查找，反之向左；
• 将左(右)边当成一个新数组，重复第一第二步，即进行递归。找到了就结束递归，或者遍历完了数组也没找到也结束递归。

2. 代码实现：

public static int find(int[] arr, int left, int right, int targetNum){
        if (left > right){
            return -1;
        }
        int mid = (left + right) / 2;
        if (arr[mid] > targetNum) {
            return find(arr, left, mid - 1, targetNum);
        } else if (arr[mid] < targetNum){
            return find(arr, mid + 1, right, targetNum);
        } else {
            return mid;
        }
 }

三、插值查找

插值查找也是二分查找，不同的是，mid的计算公式不再是mid = (left + right) / 2，变成了mid = left + (targetNum- arr[left]) / (arr[right] - arr[left]) * (right -left)，其他的都和二分查找一样。这个mid的计算公式是大佬发明的，大家有兴趣可以用数学推导一下。

四、斐波那契查找

斐波那契查找又叫黄金分割查找，黄金分割是初中学习的内容，之后又学习了斐波那契数列。

1, 1, 2, 3, 5, 8, 13……

这个就是斐波那契数列，相邻两个数的比值无限接近黄金分割值0.618。斐波那契查找就是利用斐波那契数列的这个特性来设计的查找算法。

1. 斐波那契查找介绍：

斐波那契查找和二分查找、插值查找也类似，数组也要是有序的。不同之处还是mid的计算方法。公式为：mid = left + f(k-1) - 1。对于这个公式做几点说明：

• 斐波那契数列是符合f(k) = f(k-1) + f(k-2)的一个数列，例如1, 1, 2, 3, 5, 8……；

• 要使用斐波那契查找，就要先构建一个斐波那契数列，用来获取中间索引mid；

• 斐波那契数列的长度就和原始数组保持一致即可；

• left表示原始数组左边索引，初始的时候就是0，构建好斐波那契数组，我们要让f(k-1) - 1指向数组的最后一个索引；

• 然后从斐波那契数组中根据mid = left + f(k-1) - 1来获取中间索引；

• 然后创建一个新数组，长度为f(k)，因为长度为f(k)的数组才满足f(k) = f(k-1) + f(k-2)，才能使用斐波那契数列去获取mid索引。将原始数组的所有数拷贝过去，如果f(k)的值大于原始数组的长度，那就就将超出长度的部分用原始数组的最后一个数填充；

• 根据mid索引去上面创建的新数组中获取元素进行比较；

• 如果这个数比要查找的数更小，那说明在原始数组的mid的左边，那就让right = mid - 1，同时k要减1，因为刚才我们是在斐波那契数列f(k)的位置获取的索引，在f(k)的前面，有f(k-1)个元素，将这个f(k-1)个元素继续拆分，就可以拆成f(k-1) = f(k-2) + f(k-3)，再根据mid = left + f(k-1-1) - 1重新获取mid；

• 如果这个数比要查找的数更大，就让left = mid + 1，同时k要减2，因为上面说了，斐波那契数列满足f(k) = f(k-1) + f(k-2)，在f(k)的左边，有f(k-1)个元素，右边有f(k-2)个元素，继续拆分就变成了f(k-2) = f(k-3) + f(k-4)，所以是k-2，再根据mid = left + f(k-1-2) - 1重新获取mid；

• 如果mid对应是数刚好等于被查找数，那说明找到了，mid索引就是就被查找元素的位置，但是不能直接返回mid，因为上面说了，f(k)可能比原始数组长度更长，超出部分用原始数组最后一个元素填充，如果直接返回mid，此时mid可能指向的是超出部分的元素，用这个mid去原始数组中找，就越界了，所以应该返回mid和right中较小的那个。

2. 代码实现：

public static int find(int[] arr, int targetNum){
        int left = 0; // 原始数组最左边的下标
        int right = arr.length - 1; // 原始数组最右边的下标
        int k = 0; // 表示斐波那契分割数值的下标
        int mid = 0; // 初始化mid为0
        // 获取到斐波那契数列
        int[] f = fib(arr.length);
        // 让f(k) - 1指向数组的最后一个索引
        while (f[k] - 1 < right){
            k++;
        }
        // 但是f(k)不是步长为1的递增数列，所以可能出现 f(k) - 1 的值大于原始数组最后一个索引的情况
        // 比如原始数组最大索引为4，那么此时f(k)就等于5，所以需要构造一个新数组，长度不够的部分会用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 将Arrays.copyof()方法填充的0用原始数组最后一个数填充
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }
        // 循环查找targetNum
        while (left <= right){
            mid = left + f[k-1] - 1;
            if (targetNum < temp[mid]){ // 向左查找
                right = mid - 1;
                k--;
            } else if (targetNum > temp[mid]){ // 向右查找
                left = mid + 1;
                k -= 2;
            } else { // 返回mid和right中较小的值
                return mid <= right ? mid : right;
            }
        }
        return -1;
}

/**
 * 得到一个斐波那契数列
 * @return
 */
public static int[] fib(int length){
        int[] fibArr = new int[length];
        fibArr[0] = 1;
        fibArr[1] = 1;
        for (int i = 2; i < length; i++) {
            fibArr[i] = fibArr[i-1] + fibArr[i-2];
        }
        return fibArr;
}