图解算法：四大查找算法

╰半夏微凉° 2022-11-08 09:04 10阅读 0赞

### 目录 ###

*  第一章 顺序查找算法
 *   *  1.1、算法介绍
     *  1.2、算法实现
 *  第二章 二分查找算法
 *   *  2.1、算法介绍
     *  2.2、算法实现
 *  第三章 插值查找算法
 *   *  3.1、算法介绍
     *  3.2、算法实现
 *  第四章 斐波那契查找
 *   *  4.1、算法介绍
     *  4.2、算法实现

--------------------

> 项目地址：https://gitee.com/caochenlei/algorithms

# 第一章 顺序查找算法 #

## 1.1、算法介绍 ##

顺序查找（Order Search）也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值`num`相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于`num`的结点，表示查找失败。这种查找方式效率可能并不是最好的，但是确实最容易理解和实现的。

## 1.2、算法实现 ##

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

# 第二章 二分查找算法 #

## 2.1、算法介绍 ##

二分查找（Binary Search）也称折半查找，它是一种效率较高的查找方法，但二分查找要求线性表必须采用顺序存储结构，并且表中元素按关键字有序排列。

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

## 2.2、算法实现 ##

public static int binarySearch(int[] arr, int num) { 
        return binarySearch(arr, 0, arr.length - 1, num);
    }
    
    public static int binarySearch(int[] arr, int left, int right, int num) { 
        //如果没有找到
        if (left > right || num < arr[0] || num > arr[arr.length - 1]) { 
            return -1;
        }
        //获取中间索引
        int mid = (left + right) / 2;
        //往左边递归找
        if (num < arr[mid]) { 
            return binarySearch(arr, left, mid - 1, num);
        }
        //往右边递归找
        else if (num > arr[mid]) { 
            return binarySearch(arr, mid + 1, right, num);
        }
        //数据位置找到
        else { 
            return mid;
        }
    }

# 第三章 插值查找算法 #

## 3.1、算法介绍 ##

插值查找（Insert Value Search）是二分查找的一种改良，主要是改良了`mid`的值，`mid`的值由原来的`mid = (left + right) / 2`而变成了自适应获取`mid`的值`mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left)`，上述公式是前辈们推导出来的，其余和二分查找一样。

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

## 3.2、算法实现 ##

public static int insertValueSearch(int[] arr, int num) { 
        return insertValueSearch(arr, 0, arr.length - 1, num);
    }
    
    public static int insertValueSearch(int[] arr, int left, int right, int num) { 
        //如果没有找到
        if (left > right || num < arr[0] || num > arr[arr.length - 1]) { 
            return -1;
        }
        //获取中间索引
        int mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left);
        //往左边递归找
        if (num < arr[mid]) { 
            return insertValueSearch(arr, left, mid - 1, num);
        }
        //往右边递归找
        else if (num > arr[mid]) { 
            return insertValueSearch(arr, mid + 1, right, num);
        }
        //数据位置找到
        else { 
            return mid;
        }
    }

# 第四章 斐波那契查找 #

## 4.1、算法介绍 ##

斐波那契查找（Fibonacci Search）又叫黄金分割查找，斐波那契查找和二分查找、插值查找也类似，数组也要是有序的。

不同之处还是`mid`的计算方法，`mid`不再是中间或者插值得到，而是位于黄金分割点的附近：`mid = left + f(k-1) - 1`。要使用斐波那契查找，就要先构建一个斐波那契数列，斐波那契数列的长度就和原始数组保持一致即可，主要是用来获取中间索引`mid`。

![d449d8f86f8e3aff5017adcfd04df5b9.png][]

`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`中较小的那个。

## 4.2、算法实现 ##

//获取斐波那契数列
    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;
    }
    
    //斐波那契查找算法
    public static int fibonacciSearch(int[] arr, int num) { 
        int[] f = fib(arr.length);                  //获取斐波那契的数组
        int left = 0;                               //原始数组左边的下标
        int right = arr.length - 1;                 //原始数组右边的下标
        int k = 0;                                  //斐波那契数组的下标
        while (f[k] - 1 < right) {                   //指向数组的最后索引
            k++;
        }
    
        //由于f(k)不是步长为1的递增数列，所以可能出现f(k) - 1的值大于原始数组最后一个索引的情况
        //比如原始数组最大索引为4，那么此时f(k)就等于5，所以要构造一个新数组，不够的部分会用0填充
        //如果多余部分用0填充可能会造成查找失败，因此，需要将0的部分填充为原来数组中的最后一个元素
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = right + 1; i < temp.length; i++) { 
            temp[i] = arr[right];
        }
    
    
        while (left <= right) {                      //循环查找
            int mid = left + f[k - 1] - 1;          //获取mid
            if (num < temp[mid]) {                   //往左查找
                right = mid - 1;
                k -= 1;
            } else if (num > temp[mid]) {            //往右查找
                left = mid + 1;
                k -= 2;
            } else { 
                return mid <= right ? mid : right;  //返回下标
            }
        }
        return -1;
    }

[d449d8f86f8e3aff5017adcfd04df5b9.png]: /images/20221023/451cf829f5e94dcd8ef16f16c330f6c0.png