Java查找算法：线性查找算法、二分查找算法(递归 非递归)、插值查找算法、斐波那契查找算法、思路分析、代码实现

查找算法

1、线性查找算法

对无序序列或有序序列的元素查找，线性查找算法就是对数组的遍历，找到该值的索引返回。

public class SeqSearch {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,-2,20,6};
        int index = seqSearch(arr, -1);
        System.out.println("该数的索引为"+ index);
    }

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

如果要查找到多个数，返回集合即可

2、二分(折半)查找算法 (递归)

硬性要求，在有序数组中查找。

• 首先确定中间索引mid = left+right/2即：arr[mid]
• 如果查找的值value>arr[mid]，那么就查找右边的部分，确定右边的中值，再比较
• 如果查找的值value<arr[mid]，那么就查找左边的部分，确定左边的中值，再比较
• 如果value==arr[mid]说明找到，并返回
• 如果没找到，即left>right，也退出

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,5,11,21,30};
        int index = binarySearch(arr, 0, arr.length - 1, 30);
        System.out.println(index);
    }

    public static int binarySearch(int arr[],int left, int right, int value){
        // 没找到的情况
        if (left > right){
            return -1;
        }

        // 获取此范围的中间索引
        int mid = (left+right)/2;

        if (value > arr[mid]){
            // 向右部分查找
            return binarySearch(arr, mid+1, right , value);
        }else if (value < arr[mid]){
            // 向左部分查找
            return binarySearch(arr, left, mid-1, value);
        }else {
            // 找到返回索引
            return mid;
        }
    }
}

查找数组中多个相同的值，并返回索引：

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,5,11,21,21,21,30};
        List<Integer> list = binarySearchAll(arr, 0, arr.length - 1, 21);
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

    public static List<Integer> binarySearchAll(int[] arr, int left, int right, int value){
        if (left>right){
            return new ArrayList<>();
        }

        int mid = (left+right)/2;

        if (value > arr[mid]){
            return binarySearchAll(arr, mid+1, right, value);
        }else if (arr[mid] > value){
            return binarySearchAll(arr, left, mid-1, value);
        }else {
            List<Integer> list = new ArrayList<>();
            list.add(mid);
            // 往右查找相同值
            int index = mid;
            while (true){
                index--;
                if (index < 0 || arr[index] != value){
                    break;
                }
                list.add(index);
            }
            // 往左查找相同值
            index = mid;
            while (true){
                index++;
                if (index > arr.length || arr[index] != value){
                    break;
                }
                list.add(index);
            }
            return list;
        }
    }
}

缺点：在极端情况下，如果查找的数刚好是数组的最左端或最右端，查找的次数会很多，这种情况效率不高。

3、二分查找算法 (非递归)

public class BinarySearchNoRecur {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6,7};
        System.out.println(search(arr, 7));
    }

    public static int search(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;
        while (left<=right){
            int mid = (left+right)/2;
            if (arr[mid] == target){
                return mid;
            }else if (arr[mid] < target){
                left = mid+1;
            }else if(arr[mid] > target){
                right = mid-1;
            }
        }
        return -1;
    }
}

4、插值查找算法

插值查找算法类似于二分查找：

插值公式由二分查找的公式改成如下：

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+1;
        }
        int index = insertValueSearch(arr, 0, arr.length - 1, 1);
        System.out.println(index);
    }

    public static int insertValueSearch(int[] arr, int low, int high, int value){
        // 一定要写value < arr[0] || value > arr[arr.length-1]，否则会出现越界情况
        // 一定要把小于最小值和大于最大值的数据排除掉
        if (low>high || value < arr[0] || value > arr[arr.length-1]){
            return -1;
        }

        int mid = low+(high-low)*(value-arr[low])/(arr[high]-arr[low]);

        if (value < arr[mid]){
            return insertValueSearch(arr, low, mid-1, value);
        }else if (value > arr[mid]){
            return insertValueSearch(arr, mid+1, high , value);
        }else {
            return mid;
        }
    }
}

注意：

• 对于数据量大，关键字分布比较均匀的值来说，采用插值查找算法，速度较快
• 关键字分布不均匀情况下，该算法不一定比二分查找算法好

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

斐波那契查找算法用于有序数组之上。

斐波那契数列{1, 1, 2, 3, 5, 8, 13, 21, 34, 55}，从第三个数开始，当前数等于前两个数之和。斐波拉契数列相邻两个数的比例无限接近于黄金分割值0.618

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

对F(k-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

但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可

思路分析：

斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[k]，将原查找表扩展为长度为F[k](如果要补充元素，则补充0就可以了，直到满足F[k]个元素)，完成后进行斐波那契分割，即F[k]个元素分割为前半部分F[k-1]个元素，后半部分F[k-2]个元素。

public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = {1,5,11,21,121,230};
        int index = fibonacci(arr, 230);
        System.out.println(index);
    }

    public static int fibonacci(int[] arr, int value){
        // 创建一个斐波那契数组
        int f[] = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = f[i-1]+f[i-2];
        }

        // 找到斐波那契数组中等于或略大于arr数组长度的值
        int high = arr.length-1;
        int low = 0;
        int k = 0;
        while (high > f[k]-1){
            k++;
        }

        // 创建一个长度为f[k]的临时数组，并将多出的空间，赋值为原数组最后的数值
        int temp[] = Arrays.copyOf(arr,f[k]);
        for (int i = high+1; i < temp.length; i++) {
            temp[i] = arr[high];
        }

        while (low <= high){
            // 中间索引
            int mid = low+f[k-1]-1;
            // 如果value值大于中值，就往右边查找
            // 如果value值小于中值，就往左边查找
            if (temp[mid] < value){
                low = mid+1;
                k-=2; // 减2，是因为右边的步长为2
            }else if (temp[mid] > value){
                high = mid-1;
                k--;
            }else {
                // 返回最小索引，因为temp数组可能是扩大了的，后面扩充的数字是与
                // 原数组最后一个元素是一样的，所以，当mid大于原数组的最大索引是，
                // 这个数一定是原数组的最后一个，所以返回high，否则返回mid
                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;
    }
}