数据结构——四大查找算法（工作必备）

梦里梦外; 2023-01-19 12:51 111阅读 0赞

> 在java中，常用的查找有四种
> 
> 1.  顺序（线性）查找
> 2.  二分查找折半查找
> 3.  插值查找
> 4.  斐波那契查找

### 目录 ###

*  1. 线性查找
 *  2. 二分查找
 *  3. 插值查找
 *  4. 斐波那契查找

# 1. 线性查找 #

> 线性查找是逐一比对，发现有相同值，就返回下标

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

# 2. 二分查找 #

> 使用二分查找算法的前提是序列有序
> 
> ![image-20210324205245097][]

public static int binarySearch(int[] arr, int left, int right, int findVal) { 
        if (left > right)//递归结束
            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;
    }

**问题**：如果数组中有相同的元素，只会返回一个索引值

![image-20210324204116635][]  
**解决方案**：找到mid索引时，不要马上返回，而是分别向左向右扫描所有满足查找值，假如到集合ArrayList中

public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal) { 
        if (left > right)//递归结束
            return new ArrayList<Integer>();
        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 { 
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(mid);
            int temp_left = mid - 1;//向左扫描
            while (temp_left > 0 && arr[temp_left] == findVal) { 
                arrayList.add(temp_left);
                temp_left--;
            }
            int temp_right = mid + 1;//向右扫描
            while (temp_right <= arr.length - 1 && arr[temp_right] == findVal) { 
                arrayList.add(temp_right);
                temp_right++;
            }
            return arrayList;
        }
    }

# 3. 插值查找 #

> 插值查找的前提也要求序列有序
> 
> ![image-20210324205936007][]

public static int insertValueSearch(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 insertValueSearch(arr, mid + 1, right, findVal);//向右递归
        else if (findVal < midVal)
            return insertValueSearch(arr, left, mid - 1, findVal);//向左递归
        else
            return mid;
    }

**插值查找注意事项**：

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

# 4. 斐波那契查找 #

> 又称**黄金分割法查找**，也得满足序列有序
> 
> ![image-20210324212620622][]
> 
> 斐波那契查找原理与前两种相似，仅仅改变了中间结点`mid`的位置，mid不再是中间或插值得到，而是位于**黄金分割点**附近，即 mid=low+fib(k-1)-1（**fib代表斐波那契数列**）
> 
> **原理**：
> 
>  *  由斐波那契数列 `fib[k]=fib[k-1]+fib[k-2]` 的性质，可以得到`fib[k]-1=(fib[k-1]-1)+(fib[k-2]-1)+1`
>     
>     该式说明：只要顺序表的长度为`fib[k]-1`，则可以将该表分成长度为`fib[k-1]-1`和`fib[k-2]-1`的两段，从而中间位置为`mid=low+F(k-1)-1`
>     
>     ![image-20210324235613907][]
>  *  类似的，每一子段也可以用相同的方式分割
>  *  但顺序表长度length不一定刚好等于F\[k\]-1，所以需要将原来的顺序表长度length增加至F\[k\]-1，新增的位置（从n+1到F\[k\]-1位置），都赋为n位置的值即可
>     
>     这里的k值只要能使得F\[k\]-1恰好大于或等于n即可；我们可以执行以下代码获得k的值
> 
>     while(length>fib(k)-1)
>         k++;

import java.util.Arrays;
    
    public class Test { 
        public static void main(String[] args) { 
            int[] arr = { 1, 2, 4, 5, 19, 19, 80};
            int index = fibSearch(arr, 81);
            System.out.println(index);
        }
    
        //获取斐波拉契数列
        public static int[] fib() { 
            int[] f = new int[20];
            f[0] = 1;
            f[1] = 1;
            for (int i = 2; i < 20; i++) { 
                f[i] = f[i - 1] + f[i - 2];
            }
            return f;
        }
    
        public static int fibSearch(int[] arr, int findVal) { 
            int left = 0;
            int right = arr.length - 1;
            int k = 0;//表示斐波那契数列分割数值的下标
            int mid;
            int[] fib = fib();//获得斐波那契数列
            //获取斐波那契数列分割数值的下标
            while (right > fib[k] - 1)
                k++;
            int[] temp = Arrays.copyOf(arr, fib[k]);//因为fib(k)的长度可能大于arr.length,因此需要构建一个新数组,不足的部分会用0填充
            for (int i = right + 1; i < temp.length; i++)//将不足的部分用数组的最后一个元素填充
                temp[i] = arr[right];
            while (left <= right) { 
                mid = left + fib[k - 1] - 1;
                if (findVal < temp[mid]) { //向前查找
                    right = mid - 1;
                    //全部元素fib[k] = 前面的元素fib[k-1] + 后面的元素fib[k-2]
                    //此时向前面的fib[k-1]个元素中查找,可以继续拆分fib[k-1]=fib[k-2]+fib[k-3]
                    //即下次循环mid=fib[k-2]-1
                    k--;
                } else if (findVal > temp[mid]) { //向后查找
                    left = mid + 1;
                    //全部元素fib[k] = 前面的元素fib[k-1] + 后面的元素fib[k-2]
                    //此时向后面的fib[k-2]个元素中查找,可以继续拆分fib[k-2]=fib[k-3]+fib[k-4]
                    //即下次循环mid=fib[k-3]-1
                    k -= 2;
                } else { //找到了
                    if (mid <= right)
                        return mid;
                    else
                        return right;
                }
            }
            return -1;//没找到
        }
    
    }

[image-20210324205245097]: https://gitee.com/zhong_siru/images/raw/master//img/image-20210324205245097.png
[image-20210324204116635]: /images/20221021/53043b75d88c40b5b08be23a468c2325.png
[image-20210324205936007]: https://gitee.com/zhong_siru/images/raw/master//img/image-20210324205936007.png
[image-20210324212620622]: https://gitee.com/zhong_siru/images/raw/master//img/image-20210324212620622.png
[image-20210324235613907]: https://gitee.com/zhong_siru/images/raw/master//img/image-20210324235613907.png