算法与数据结构之查找算法

查找算法

查找算法介绍

在 java 中，我们常用的查找有四种:

1. 顺序(线性)查找
2. 二分查找/折半查找
3. 插值查找
4. 斐波那契查

线性查找算法

有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】 要求: 如果找到了，就提 示找到，并给出下标值。

package com.atguigu.search;

public class SeqSearch {

    public static void main(String[] args) {
        int[] arr={1,8, 10, 89, 1000, 1234};
        int seqSearch = seqSearch(arr, 89);
        if (seqSearch==-1) {
            System.out.println("没有找到");
        }else {
            System.out.println("找到，下表为="+seqSearch);
            
        }
    }
    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,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下 标，如果没有就提示”没有这个数”。

二分查找算法的思路

二分查找的代码

说明：增加了找到所有的满足条件的元素下标: 课后思考题：{1,8,10,345,15,78,78,78,23,67,78}当一个有序数组中，有多个相同的数值时，如何将所有的数值 都查找到，比如这里的 78.

• 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 78
• 思路分析
• 1. 在找到 mid 索引值，不要马上返回
• 2. 向 mid 索引值的左边扫描，将所有满足 78， 的元素的下标，加入到集合 ArrayList
• 3. 向 mid 索引值的右边扫描，将所有满足 78， 的元素的下标，加入到集合 ArrayList
• 4. 将 Arraylist 返回

package com.atguigu.search;

import java.util.ArrayList;

public class BinarySearch {//二分查找多个相同值
public static ArrayList<Integer> binarySearch(int[] arr,int left,int right,int findVal) {
    int mid=(left+right)/2;
    int midVal=arr[mid];
    if (left>right) {
        return new ArrayList<Integer>();
    }
    if (findVal>midVal) {
        return binarySearch(arr, mid+1, right, findVal);
        
    }else if (findVal<midVal) {
        return binarySearch(arr, left, mid-1, findVal);
        
    }else {
        ArrayList<Integer> list = new ArrayList<>();
        int temp=mid-1;
        while (true) {
            if (temp<0 || arr[temp]!=findVal) {
                break;
            }
            list.add(temp);
            temp-=1;
        }
        list.add(mid);
        temp=mid+1;
        while (true) {
            if (temp>arr.length-1 || arr[temp]!=findVal) {
                break;
            }
            list.add(temp);
            temp+=1;
        }
        return list;
    }    
    }
    public static void main(String[] args) {
        int[] arr =new int[]{1,8,10,345,15,78,78,78,23,67,78};
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j]>arr[j+1]) {
                    int temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"\t");
        }
        ArrayList<Integer> search = binarySearch(arr, 0, arr.length-1, 78);
        System.out.println();
        System.out.println(search);
}
}

插值查找算法

插值查找原理介绍:

1. 插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
2. 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 findVal

1. int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/
   对应前面的代码公式：
   int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
2. 举例说明插值查找算法 1-100 的数组

插值查找应用案例：

请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示”没有这个数”。
代码实现:

package com.atguigu.search;

import java.util.Arrays;

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;
//        }
//        System.out.println(Arrays.toString(arr));
        int[] arr={1,6,45,65,123,234,345,676};
        int index = insertValueSearch(arr, 0, arr.length-1, 65);
        System.out.println("index= "+index);
        System.out.println("*******");
        int index1 = binarySearch(arr, 0, arr.length-1, 65);
        System.out.println("index2="+index1);
        
    }
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
    System.out.println("插值查找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, mid+1, right, findVal);
    }else if (findVal<midVal) {
        return insertValueSearch(arr, left, mid-1, findVal);
    }else {
        return mid;
    }
    
}
public static int binarySearch(int[] arr,int left,int right,int findVal) {
    System.out.println("查找1次");
    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;
    }
    
}
}

插值查找注意事项：

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

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

斐波那契(黄金分割法)查找基本介绍:

1. 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位
   数字的近似值是 0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
2. 斐波那契数列 {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 的理解：
  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 的两段，即如上图所示。从而中间
     尚硅谷 Java 数据结构和算法
     更多 Java –大数据 –前端 –python 人工智能 -区块链资料下载，可访问百度：尚硅谷官网 第 181页
     位置为 mid=low+F(k-1)-1
  2. 类似的，每一子段也可以用相同的方式分割
  3. 但顺序表长度 n 不一定刚好等于 F[k]-1，所以需要将原来的顺序表长度 n 增加至 F[k]-1。这里的 k 值只要能使
     得 F[k]-1 恰好大于或等于 n 即可，由以下代码得到,顺序表长度增加后，新增的位置（从 n+1 到 F[k]-1 位置），
     都赋为 n 位置的值即可。
     while(n>fib(k)-1)
     k++;

斐波那契查找应用案例：

请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求
出下标，如果没有就提示”没有这个数”。
代码实现:

package com.atguigu.search;

import java.util.Arrays;
//用斐波那契数列来存储数组元素个数
public class FeibonacciSearch {
    public static int maxSize=20;
        
    public static void main(String[] args) {
        
        int []arr={1,8,10,89,1000,1234};//数组元素个数是6
        System.out.println("index: "+fibSearch(arr, 1000));
        
    }
    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 (a.length>f[k]-1) {// 获取斐波那契分割数值下标 
            k++;
        }
        int[] temp=Arrays.copyOf(a, f[k]);
        // 序列补充至f[k]个元素  
        // 补充的元素值为最后一个元素的值 
        for (int i = high+1; i < temp.length; i++) {
            temp[i]=a[high];
        }
         for (int i: temp) {  //数组变为 1 8 10 89 1000 1234 1234 1234 
                System.out.print(i + " ");  
            }  
            System.out.println();  
        while (low<=high) {
             // low：起始位置  
            // 前半部分有f[k-1]个元素，由于下标从0开始  
            // 则-1 获取 黄金分割位置元素的下标 
            mid=low+f[k-1]-1;
            if(key<temp[mid]){ // 查找前半部分，高位指针移动 
                high=mid-1;
                // （全部元素） = （前半部分）+（后半部分）  
                // f[k] = f[k-1] + f[k-2]  
                // 因为前半部分有f[k-1]个元素，继续拆分f[k-1]=f[k-2]+f[k-3],所以 k = k-1  
                k--;
            }else if(key>temp[mid]){  // 查找后半部分，高位指针移动  
                low=mid+1;
                // （全部元素） = （前半部分）+（后半部分）  
                // f[k] = f[k-1] + f[k-2]  
                // 因为后半部分有f[k-2]个元素，继续拆分为f[k-2]=f[k-3]+f[k-4]所以 k = k-2  
                k-=2;
            }else { // 如果为真则找到相应的位置  
                if (mid<=high) {
                    return mid;
                }else {
                    // 出现这种情况是查找到补充的元素  
                    // 而补充的元素与high位置的元素一样  
                    return high;
                }
            }
        }
        return -1;    
    }
}