数据结构与算法-查找算法 | 尚硅谷韩顺平笔记

卒获有所闻

453人浏览 · 2022-09-25 18:04:32

卒获有所闻 · 2022-09-25 18:04:32 发布

一、顺序查找（线性查找）

顺序查找太简单了，没什么好说的，直接循环找到等于的就返回，没有找到就返回-1

代码实现

//顺序查找(线性查找)
public class SeqSearch {
    public static void main(String[] args) {
        int arr[] = {1,9,11,-1,34,89}; //没有顺序的数组
        int index = seqSearch(arr,11);
        if (index == -1){
            System.out.println("没有找到");
        }else{
            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;
    }
}

二、二分查找（折半查找）

使用二分查找的前提是这个数组是有序的

思路分析

1、首先确定改数组的中间的下标 mid = (left+right)/2

2、然后让需要查找的数findVal和arr[mid]比较

如果findVal>arr[mid]，说明你要查找的数在mid右边，递归向右查询
如果findVal<arr[mid]，说明你要查找的数在mid左边，递归向左查询
如果findVal==arr[mid]，说明找到了直接返回

3、找到就结束递归

4、递归完还没找到也结束递归

代码实现 (递归）

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,1000};
        int resIndex = binarySearch(arr,0, arr.length-1,88 );
        if (resIndex!=-1){
            System.out.println("要找的值索引为："+resIndex);
        }else {
            System.out.println("数组没有这个数");
        }
    }

    //二分查找算法
    public static int binarySearch(int[] arr,int left,int right,int findVal){

        //当left>right说明递归完整个数组了还是没有找到
        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;
        }
    }
}

优化

我们又多了个需求：要找一个数，如果数组有很多这个相同的数，那么我们都要找出来

思路：在找到结果的时候，我们先不急着返回，先向左和向右扫描，将满足的都加入集合中

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,1000,1000,1000};
        ArrayList resIndexList = binarySearch(arr,0, arr.length-1,1000 );
        System.out.println(resIndexList);
    }

    //二分查找算法
    public static ArrayList<Integer> binarySearch(int[] arr,int left,int right,int findVal){

        //当left>right说明递归完整个数组了还是没有找到
        if (left>right){
            return new ArrayList<>();
        }
        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> resIndexlist = new ArrayList<>();
            int temp = mid-1;
            while(true){
                if (temp <0 || arr[temp]!=findVal){
                    break;
                }
                //否则放入集合中
                resIndexlist.add(temp);
                temp-=1; //左移
            }
            resIndexlist.add(mid);
            temp = mid+1;
            while(true){
                if (temp > arr.length-1 || arr[temp]!=findVal){
                    break;
                }
                //否则放入集合中
                resIndexlist.add(temp);
                temp+=1; //左移
            }
            resIndexlist.add(mid);
            return resIndexlist;
        }
    }
}

代码实现（非递归）

public class BinarySearchNoRecur {

    public static void main(String[] args) {
        int[] arr = {1,3,8,10,11,67,100};
        int index=binarySearch(arr,11);
        System.out.println(index);
    }

    /**
     *
     * @param arr 待查找的数组
     * @param target  需要查找的数
     * @return 返回对应的下标，-1表示没有找到
     */
    public static int binarySearch(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){
                right = mid-1; //需要向左边查找
            }else {
                left = mid+1;
            }
        }
        return -1;
    }
}

三、插值查找算法

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找

是对二分查找算法进行的优化，如果每次折半其实效率并不高，所以我们对mid的公式进行优化

int mid = left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left])

他是一种自适应的写法因为他本身的值也参加了mid的运算

代码实现

public class InsertValueSearch {
    public static void main(String[] args) {
        int arr[] = new int[100];
        for (int i=0;i<100;i++){
            arr[i]=i+1;
        }
        int res = insertValueSearch(arr,0, arr.length-1, 99);
        System.out.println(res);
    }

    //插值查找也要求数组有序
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        //findVal<arr[0] || findVal>arr[arr.length-1]是必须要加的 否则可能越界
        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, left, mid-1, findVal);
        } else if (findVal>midVal) {
            return insertValueSearch(arr, mid+1, right, findVal);
        } else {
            return mid;
        }
    }
}

注意事项

对于数据量较大，关键字分布比较均匀的查找来说，采用插值查找，速度比较快。

关键词分布不均匀的情况下，改方法不一定比折半快

四、斐波那契查找（黄金分割法）

斐波那契数列{1,1,2,3,5,8,13,21,34,55}

发现斐波那契数列相邻两个数的比例，无限接近黄金分割值0.618

原理分析

原理与前面两种相似，仅仅改变了中间点mid的位置，mid不再是中间或者插值得到，而是位于黄金分割点附近

根据对斐波那契数列 F[k] = F[K-1] + F[K-2] 可得 (F[k]-1)=(F[k-1]-1)+(F[k-1]-1)

说明：只要顺序表长度为F[k]-1 就可以分为(F[k-1]-1)和(F[k-1]-1)两段，如图

所以中间值 mid = low + F[K-1]- 1

注意：我们的顺序表不一定等于F[k]-1 所以我们需要把他从n扩充到F[K]-1 （这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。）

while(n>fib(k)-1)
    k++;

代码实现

public class FibonacciSearch {
    public static int maxSize = 20;
    public static void main(String[] args) {
        int [] arr = {1,8,10,89,1000,1234};
        System.out.println("index = "+fibSearch(arr,1));
    }

    //因为后面我们mid=low+f(k-1)-1 需要斐波那契数列 因此我们需要得到一个斐波那契数组
    //非递归得斐波那契数列（效率高些）
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i=2;i<maxSize;i++){
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    //编写斐波那契查找算法
    public static int fibSearch(int[] a,int key){
        int low = 0;
        int high = a.length-1;
        int k = 0; //斐波那契分割数值的下标
        int mid = 0;
        int f[] = fib();//获取斐波那契数列
        //获取斐波那契分割数列的下标
        while (high>f[k]-1){
            k++;
        }
        //因为f[k]值可能大于a的长度，因此我们需要使用Array构造新的数组并指向a[]
        int[] temp = Arrays.copyOf(a,f[k]); //不足的部分用0填充
        //实际用a数组的最后一个数来填充数组
        for (int i = high +1;i< temp.length;i++){
            temp[i] = a[high];
        }

        //使用while循环处理，得到我们的数key
        while(low<=high){
            mid = low+f[k-1]-1;
            if (key<temp[mid]){ //说明向左找
                high = mid -1 ;
                //1、全部的元素=前面的元素+后面的元素
                //2、f[k] = f[k-1]+f[k-2]
                //因为前面有f[k-1]个元素，所以可以继续拆分  f[k-1] = f[k-2]+f[k-3]
                //即在f[k-1]的前面继续查找，k--
                //即下次循环的时候 mid = f[k-1-1]-1
                k --;
            }else if (key> temp[mid]){
                high = mid+1;
                //1、全部的元素=前面的元素+后面的元素
                //2、f[k] = f[k-1]+f[k-2]
                //3、因为后面有f[k-2]，所以可以继续拆分 f[k-1] = f[k-3] +f[k-4]
                //4、即在f[k-2]的前面进行查找 k-=2
                //即下次循环的时候 mid = f[k-1-2]-1
                k-=2;
            }else { //找到
                if(mid<=high){
                    return mid;
                }else{
                    return high;//因为填充了 high可能找的就是那个high
                }

            }
        }
        return -1;
    }
}