• 查找算法.

    在java中,常用的查找有四种

    • 顺序查找
    • 二分查找/折半查找
    • 插值插值
    • 斐波拉查找

    线性查找算法

    有一个数列(1,8,10,89,1000,1234),判断数列中是否包含此名称[顺序查找],要求:如果找到了,就提示找到,并给出下标值,

    思路:如果查到全部符合条件的值;

    注意我们的线性查找我们找到一个就放回,如果里面有两个或多个相同的呢,我们可以返回值是一个list集合,然后我们遍历的时候全部遍历就行.

    package com.atguigu.search;

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("没有找到11");
        }
        System.out.println("找到了,下标为"+index);
    }


    /**
     * 这里我们实现的线性查找是找到一个满足条件的值就返回,
     * @param arr
     * @param value
     * @return
     */
    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    二分查找

    请对一个有序数组进行二分查找{1,8,10,89,1000,1234},输入一个数,看看该数组是否存在此数,并且要求出下标,如果没有就提示"没有这个数"

    二分查找的思路
    • 首先确定该数组中间的下标
      • mid=(left+right)/2
    • 然后让需要查找的数findVal和arr[mid]比较
      • findVal>arr[mid],说明你要查找的数在mid的右边,因此需要递归向右查找
      • findVal
      • findVal=arr[mid],说明找到了,找到就返回
        什么时候结束递归
    • 找到就结束递归
    • 递归完整个数组,仍然没有找到findVal也要结束递归,此时的结束条件
      • 当left>right就需要退出,这个是我们没有找到结束的递归条件
    二分查找的基本写法
    
package com.atguigu.search;
//注意二分查找的前提是数组必须是有序的(从小到大,从大到小都可以)
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};

        int resIndex=binarySearch(arr,0,arr.length-1,88);
        System.out.println(resIndex);
    }


    /***
     * 二分查找算法
     * @param arr  数组
     * @param left  左边的索引
     * @param right  右边的索引
     * @param findVal 要查找的值
     * @return  如果找到放回下标,如果没有找到,返回-1
     */

    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;
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    二分查找的升级写法

    当一个数组中{1,8,10,89,1000,1000,1234} 当一个有序数组中,有多个相同的数值时,如何将多有数组都查找到,比如这里的1000

    思路
    • 在找到mid值时,不要马上返回,先向mid这个索引值的左边扫描,将所有满足1000的原始的下标加入到一个集合中,ArrayList
    • 向mid索引值的右边扫描,将所有满足1000的元素下标,加入到集合ArrayList
    • 将ArrayList集合返回
    
package com.atguigu.search;

import java.util.ArrayList;
import java.util.List;

//注意二分查找的前提是数组必须是有序的(从小到大,从大到小都可以)
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};
        int[] arr1={1,8,10,89,1000,1000,1234};

        int resIndex=binarySearch(arr,0,arr.length-1,88);
        System.out.println(resIndex);

        ArrayList<Integer> list=binarySearch1(arr1,0,arr1.length-1,1000);
        System.out.println(list);
    }


    /***
     * 二分查找算法
     * @param arr  数组
     * @param left  左边的索引
     * @param right  右边的索引
     * @param findVal 要查找的值
     * @return  如果找到放回下标,如果没有找到,返回-1
     */

    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 static ArrayList<Integer> binarySearch1(int[] arr,int left,int right,int findVal){

        //当left>right时,说明递归完毕,但是没有找到
        if(left>right){
            return new ArrayList<Integer>();//返回一个空的ArrayList
        }
        int mid=(left+right)/2;
        int midVal=arr[mid];
        if (findVal>midVal){ //向右边递归
            return binarySearch1(arr,mid+1,right,findVal);
        }else if(findVal<midVal){//向左递归
            return binarySearch1(arr,left,mid-1,findVal);
        }else {

            ArrayList<Integer> arrayList=new ArrayList<Integer>();
            //向mid索引值左边扫描,满足1000,的元素下标,加入到集合
            int temp=mid-1;
            while (true){
                if(temp<0||arr[temp]!=findVal){//退出
                    break;
                }
                //否则将temp放入到集合中
                arrayList.add(temp);//这里用来自动装箱
                temp-=1;//temp左移动
            }

            //
            //向mid索引值右边边扫描,满足1000,的元素下标,加入到集合
             temp=mid+1;
            while (true){
                if(temp>arr.length-1||arr[temp]!=findVal){//退出
                    break;
                }
                //否则将temp放入到集合中
                arrayList.add(temp);//这里用来自动装箱
                temp+=1;//temp右边移动
            }
            arrayList.add(mid);
            return arrayList ;
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    插值查找

    • 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找.
    • 将折半查找中的求mid索引的公式,low表示左边索引,high表示右边索引
    • mid=(low+high)/2=low+1/2(high-low) 改为mid=low+(key-a[low])/(a[high]-a[low]*(high-low))
    • 公式里面的可以就是我们要查找的值,findVal
      在这里插入图片描述
    • int midIndex=low+(high-low)*(key-arr[low])/(arr[high]-arr[low]);/插值索引 /
    • 对应前面的代码,我们的公式变成了
    • int mid=left+(right-left)*(findVal-arr[Left])/(arr[right]-arr[left])
    插值查找算法的举例说明

    数组arr={1,2,3,4…,100}
    假入我们需要查找的值是1
    使用二分查找我们需要多次递归我们才能找到1
    使用插值查找算法
    int mid=left+(right-left)(findVal-arr[left])/(arr[right]-arr[left])
    int mid=0+(99-0)    (1-1)/(100-1)=0+99*0/99=0

    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;
        }
        int index=insertValueSearch(arr,0,arr.length-1,100);
        System.out.println("index="+index);
    }

    //编写插值查找算法

    /**
     *
     * @param arr 数组
     * @param left  左边索引
     * @param right 右边索引
     * @param findVal  查找值
     * @return 如果找到返回对应下标,没有找到返回-1
     */
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        //注意这个判断必须有,不然可能会越界
        if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
            //插值查找算法也要求数组是有序的,所有上面的条件我们直接返回-1
            return -1;
        }
        //求出mid
        int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal=arr[mid];
        if(findVal>midVal){//如果要查的值比我们arr[mid]大,那么我们向右边递归查找
            return insertValueSearch(arr,mid+1,right,findVal);

        }else if(findVal<midVal){//向左边递归查找
            return insertValueSearch(arr,left,mid-1,findVal);
        }else {
            return mid;
        }

    }

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    插值查找注意事项

    插值查找对于数据量较大关键字分布均匀的查找表来说,采用插值查找,速度较快
    关键字分布不均匀的请求下,不一定比折半查找要好.

    斐波拉契(也叫黄金分割法)

    • 黄金分割点是指把一条线段分割成两个部分,使其中一部分与全长之比等于另外一部分与这部分之比,取其前三位数字的近视值是0.618,由于按此比例设计的造型十分美丽,因此称为黄金分割,也称中外比,这是一个神奇的数字,会带来意想不到的效果
    • 斐波拉契数列{1,1,2,3,5,8,13,21,34,55}发现斐波拉契数列的两个相邻数的比例,无限接近黄金分割值0.618
    斐波拉契的原理与前两种相似

    仅仅改变了中间点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即**(mid=low+F(k-1)-1)(F代表斐波拉契数列,K代表的第几个元素),如图所示:
    在这里插入图片描述
    对F(k-1)-1的理解
    1,由于斐波拉契数列F[k]=F[k-1]+F[k-2]的性质得到,可以得到**(F[k-1]-1)+(F[k-2]-1) +1,该式说明,只要顺序表的长度为F[k]-1,则可以将该表分为长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示,从而中间位置mid=low+F(K-1)-1
    2.类似的,每一子段也可以用相同的方式分割
    3,但顺序长度n不一定刚好等于F[k]-1,所有需要将原来顺序表长度增加到F[k]-1,这里的k值只要能是的F[k]-1,恰好大于或等于n即可,有以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n即值即可.
    while(n>fib[k]-1){
    k++}
    这种就是需要对原来的数组进行扩容

    package com.atguigu.search;

import java.util.Arrays;

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,8));
    }
    
    //因为后面我们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;
    }
    
    //编写斐波拉契查找算法
//使用非递归的方式编写算法
    /**
     * 
     * @param a 数组
     * @param key 我们需要查找的关键码
     * @return 返回对应的下标,如果没有返回-1
     */
    public static int fibSearch(int[] a,int key) {
        int low = 0;
        int high = a.length - 1;
        int k = 0;//表示斐波拉契分割数值对应的下标
        int mid = 0;//存放我们的mid值
        int[] f = fib();//获取到斐波拉契数列
        //获取到斐波拉契分割数值的下标
        while (high > f[k] - 1) {
            k++;
        }
        //因为f[k]这个值可能大于我们数组a的长度,因此我们需要使用一个Arrays类,构造一个新的数组,并指向temp
        //Arrays.拷贝后,不足的部分用0填充
        int[] temp = Arrays.copyOf(a, f[k]);
        //实际上需要使用a数组最后的数填充 temp
        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;
                //为什么是k--
                // 说明
                //1,全部元素等于前面元素加上我们的后面的元素
                //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]) {//向数组的后面(右边)查找
                low = mid + 1;
                //问什么是k-2
                //说明
                //全部元素前面加后面
                //f[k]=f[k=1]+f[k-2]那拿到
                //因为后面我们后面还有f[k-2]个元素,所有我们可以继续拆分f[k-1]=f[k-3]+f[k-4]
                //即在f[k-2]的前面查找k-=2
                //即下次循环mid=f[k-1-2]-1;
                k -= 2;
            } else {//找到
                //需要确定,返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    斐波拉契算法小结

    斐波拉契仍然是有序的,还有对于对F(k-1)-1的理解要好好理解.
    然后多看代码.

  • 相关阅读:
    GDB/MI断点信息
    Java如何解决浮点数计算不精确问题
    oracle 日期
    linux高级篇基础理论五（用户安全，口令设置，JR暴力破解用户密码，NMAP端口扫描）
    CC-Proxy配置实验室网络代理服务器
    pix2tex - LaTeX OCR 安装使用记录
    斯坦福JSKarel编程机器人使用介绍
    MYSQL 数据库对比 工具类
    horizontal image flip(Neon优化)
    使用html+css实现一个静态页面（含源码）
  • 原文地址：https://blog.csdn.net/weixin_51599093/article/details/127760618