写在前面

• 数据结构全文

查找算法

• 顺序（线性）查找
• 二分查找/折半查找
• 插值查找
• 斐波那契（黄金分割）查找

顺序查找

public static int seqSearch(int[] arr, int val) {    //逐一比对    for (int i = 0; i < arr.length; i++) {        if (val == arr[i]) {            return i;        }    }    return -1;}复制代码

二分查找

• 针对有序数组

public static int binarySearch(int[] arr, int left, int right, int findVal) {    //当此时两个值，且都不=findVal，那么此时mid=left，传进去递归的就一个值，    //如果findVal > midVal 且此时right=left，进入递归后，    //就会出现left>right的情况，再进入一层递归才会跳出    //如果findVal < midVal 进入递归后，将直接跳出    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {        return -1;    }    int mid = (left + right) / 2;    int midVal = arr[mid];    if (findVal > midVal) {        return binarySearch(arr, mid + 1, right, findVal);    } else if (findVal < midVal) {        return binarySearch(arr, left, mid - 1, findVal);    } else {        return mid;    }}复制代码

数组中有相同的数

• 找到mid值时不要马上返回，向左右继续扫描，把满足arr[temp] == findVal都找出来

public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {        return new ArrayList<>();    }    int mid = (left + right) / 2;    int midVal = arr[mid];    if (findVal > midVal) {        return binarySearch2(arr, mid + 1, right, findVal);    } else if (findVal < midVal) {        return binarySearch2(arr, left, mid - 1, findVal);    } else {        //mid == findVal        List<Integer> resIndexlist = new ArrayList<>();        //向左扫描        int temp = mid - 1;        while (temp > 0 && arr[temp] == findVal) {            resIndexlist.add(temp);            temp -= 1;        }        resIndexlist.add(mid);        //向右扫描        temp = mid + 1;        while (temp < arr.length && arr[temp] == findVal) {            resIndexlist.add(temp);            temp += 1;        }        return resIndexlist;    }}复制代码

插值查找

• 优化二分查找，适用于分布比较均匀，接近于一元一次函数，如果不接近，不一定比二分查找好，说不定需要查找的值与理想值，差距较大
• 自适应mid，调整获取mid的公式int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left])，趋近于要找的值
• 本质上就是，在left与right之间画一条一元一次方程，x轴为值，y轴为索引。假设在arr[0]与arr[arr.length - 1]连接，那么这条线上的所有值，为理想上索引和值得分布，那么(right - left) / (arr[right] - arr[left])是斜率，通过(findVal - arr[left])理想状态中，findVal在这条函数上，可以找到准确的mid值，但是在实际中，也可以找到周围的mid值
• 公式变换，(mid - left) / (right - left) = (findVal - arr[left]) / (arr[right] - arr[left]) -> (mid - left) / (findVal - arr[left]) = (right - left) / (arr[right] - arr[left])，放在坐标系上就是(findVal, mid)、arr[left], left与arr[right], right三个点的关系

public static int insertSearch(int[] arr, int left, int right, int findVal) {    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {        return -1;    }    int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);    int midVal = arr[mid];    if (findVal > midVal) {        //向右        return insertSearch(arr, mid + 1, right, findVal);    } else if (findVal < midVal) {        //向左        return insertSearch(arr, left, mid - 1, findVal);    } else {        return mid;    }}复制代码

斐波那契查找

• 黄金分割查找算法
• 斐波那契数列，相邻两个数的比例无限接近0.618
• 修改mid的获取，将一个顺序表的长度分割为两段符合黄金分割比例的长度，假设原表长度F[k]，根据斐波那契数列性质F[k]=F[k-1]+F[k-2]，那么也就是说，将这个表分割成长度为F[k-1]和F[k-2]的两部分，得下标(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1，，那么中间mid的下标就是mid=low+F[k-1]-1，low为起始的偏移
• 如果表的长度n不一定为F[k]，那么就要将表长度增加至满足要求

public static int maxSize = 20;//获取斐波那契数列public static int[] fib() {    int[] f = new int[maxSize];    f[0] = 0;    f[1] = 1;    for (int i = 2; i < maxSize ; i++) {        f[i] = f[i - 1] + f[i - 2];    }    return f;}复制代码

• 斐波那契查找

/** * @param arr 目标数组 * @param key 要查找的值 * @return */public static int fibSearch(int[] arr, int key){    int low = 0;    int high = arr.length - 1;    int k = 0; //斐波那契分割的数列下标    int mid = 0; //存放mid    int f[] = fib(); //获取斐波那契数列 0、1、1、2、3、5、8、13、21、34...    //获取斐波那契数列的下标，high代表数组的长度，在数列中找到相应的数组长度的那个值的下标    //例如 high=6 arr.length=7，那么数列中f[6]对应为8，下标就为6，但是实际上f[k]>arr    while (arr.length > f[k] || k < 2) {        k++;    }    //如果f[k] > arr的长度，构造一个新的数组，使新的数组长度为数列中的值，多出来的部分用0填充    //例如，arr.length=7，而对应f[6]=8，那么需要增加数组的长度    int[] temp = Arrays.copyOf(arr, f[k]);    //但是不能用0填充，需要用a数组最后的数值填充temp    for (int i = high + 1; i < temp.length; i++) {        temp[i] = arr[high];    }    //找到目标数    while (low <= high) {        //f[k-1]为前面那段的长度，-1 + low为获取下标，第一次长度为8 对应长度前5，后3        mid = low + f[k - 1] -1;        if (key < temp[mid] && k >= 0) {            //向前面查找，但是mid后面包括mid就不查找了            high = mid - 1;            //前面有f[k-1]元素，需要继续拆分 f[k-1] = f[k-2] + f[k-3]            //例如，此时数组元素个数为8，mid为下标为4，low至mid有5个元素`f[k-1]`的长度            //此时，向前查找，要将这5个元素再次分割，那么数组长度就为`f[k-1]`            //对应的，mid=f[k-1-1]-1 + low;            k --;        } else if (key > temp[mid]) {            //向后查找            low = mid + 1;            //后面的长度为`f[k-2]`，要针对后面的长度进行分割            //mid=f[k-2-1]-1 + low            k -= 2;        } else {            if (mid <= high) {                return mid;            } else {                //如果mid>high，表示已经在查找后面填充的元素，那么要返回原始数组最长的下标                return high;            }        }    }    return -1;}

作者：99永远差一分
链接：
https://juejin.cn/post/7004654626096021535
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。