投稿
  1. 极客之音首页
  2. 后端漫谈

Java中常用查找算法及示例-顺序查找、二分查找、差值查找、斐波那契查找

飞熊 • • 后端漫谈 • 阅读 192

生活中，最使人疲惫的往往不是道路的遥远，而是心中的郁闷;最使人痛苦的往往不是生活的不幸，而是希望的破灭;最使人颓废的往往不是前途的坎坷，而是自信的丧失;最使人绝望的往往不是挫折的打击，而是心灵的死亡。所以我们要有自己的梦想，让梦想的星光指引着我们走出落漠，走出惆怅，带着我们走进自己的理想。

导读：本篇文章讲解 Java中常用查找算法及示例-顺序查找、二分查找、差值查找、斐波那契查找，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com，来源：原文

场景

Java中对数据需要进行查找，归纳整理常用查找算法及示例。

注：

博客：
https://blog.csdn.net/badao_liumang_qizhi 

实现

1、顺序查找

顺序查找法就是将数据一项一项地按照顺序逐个查找，所以不管数据顺序如何，

都得从头到位遍历一遍。该方法的优点就是文件在查找前不需要进行任何处理与排序，

缺点就是查找速度较慢。

示例代码:

public class ShunXv {
    public static void main(String args[]) throws IOException
    {
        String strM;
        BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
        int data[] =new int[100];
        int i,j,find,val=0;
        for (i=0;i<80;i++)
            data[i]=(((int)(Math.random()*150))%150+1);
        while (val!=-1)
        {
            find=0;
            System.out.print("请输入要查找的键值(1~150)，输入-1则退出程序：");
            strM=keyin.readLine();
            val=Integer.parseInt(strM);
            for (i=0;i<80;i++)
            {
                if(data[i]==val)
                {
                    System.out.print("在第"+(i+1)+"个位置找到键值 ["+data[i]+"]\n");
                    find++;
                }
            }
            if(find==0 && val !=-1)
                System.out.print("######没有找到 ["+val+"]######\n");
        }
        System.out.print("数据内容：\n");
        for(i=0;i<10;i++)
        {
            for(j=0;j<8;j++)
                System.out.print(i*8+j+1+"["+data[i*8+j]+"]  ");
            System.out.print("\n");
        }
    }
}

2、二分查找法

如果要查找的数据已经实现排好序了，就可以使用二分查找法来进行查找。二分查找就是将数据分割成两份，

再比较键值与中间值的大小。如果键值小于中间值，就可以确定要查找的数据再前半部分，否则在后半部分，

如此分割数次直到找到或确定不存在为止。

示例代码:

public class ErFen {
    public static void main(String args[]) throws IOException
    {
        int i,j,val=1,num;
        int data[] =new int[50];
        String strM;
        BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
        for (i=0;i<50;i++)
        {
            data[i]=val;
            val+=((int)(Math.random()*100)%5+1);
        }
        while (true)
        {
            num=0;
            System.out.print("请输入查找键值(1-150)，输入-1结束：");
            strM=keyin.readLine();
            val=Integer.parseInt(strM);
            if(val==-1)
                break;
            num=bin_search(data,val);
            if(num==-1)
                System.out.print("##### 没有找到["+val+"] #####\n");
            else
                System.out.print("在第 "+(num+1)+"个位置找到 ["+data[num]+"]\n");
        }
        System.out.print("数据内容：\n");
        for(i=0;i<5;i++)
        {
            for(j=0;j<10;j++)
                System.out.print((i*10+j+1)+"-"+data[i*10+j]+" ");
            System.out.print("\n");
        }
        System.out.print("\n");
    }

    public static int bin_search(int data[],int val)
    {
        int low,mid,high;
        low=0;
        high=49;
        System.out.print("正在查找......\n");
        while(low <= high && val !=-1)
        {
            mid=(low+high)/2;
            if(val<data[mid])
            {
                System.out.print(val+" 介于位置 "+(low+1)+"["+data[low]+"]及中间值 "+(mid+1)+"["+data[mid]+"]，找左半边\n");
                high=mid-1;
            }
            else if(val>data[mid])
            {
                System.out.print(val+" 介于中间值位置 "+(mid+1)+"["+data[mid]+"]及 "+(high+1)+"["+data[high]+"]，找右半边\n");
                low=mid+1;
            }
            else
                return mid;
        }
        return -1;
    }
}

3、差值查找法

差值查找法是二分法的改进版，按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。

差值查找法的公式为:mid = low +((key – data[low]) / (data[high] – data[low])) *(high – low)

其中key是要查找的键值，data[high]、data[low]是剩余待查找记录中的最大最小值。

一般而言，差值查找法优先于顺序查找法，数据的分布越平均，查找速度越快。

示例代码:

public class ChaZhi {
    public static void main(String args[]) throws IOException
    {
        int i,j,val=1,num;
        int data[]=new int[50];
        String strM;
        BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
        for (i=0;i<50;i++)
        {
            data[i]=val;
            val+=((int)(Math.random()*100)%5+1);
        }
        while(true)
        {
            num=0;
            System.out.print("请输入查找键值(1-"+data[49]+")，输入-1结束：");
            strM=keyin.readLine();
            val=Integer.parseInt(strM);
            if(val==-1)
                break;
            num=interpolation(data,val);
            if(num==-1)
                System.out.print("##### 没有找到["+val+"] #####\n");
            else
                System.out.print("在第 "+(num+1)+"个位置找到 ["+data[num]+"]\n");
        }
        System.out.print("数据内容：\n");
        for(i=0;i<5;i++)
        {
            for(j=0;j<10;j++)
                System.out.print((i*10+j+1)+"-"+data[i*10+j]+" ");
            System.out.print("\n");
        }
    }

    public static int interpolation(int data[],int val)
    {
        int low,mid,high;
        low=0;
        high=49;
        int tmp;
        System.out.print("正在查找......\n");
        while(low<= high && val !=-1 )
        {
            tmp=(int)((float)(val-data[low])*(high-low)/(data[high]-data[low]));
            mid=low+tmp;   //插值查找法公式
            if (mid>50 || mid<-1)
                return -1;
            if (val<data[low] && val<data[high])
                return -1;
            else if (val>data[low] && val>data[high])
                return-1;
            if (val==data[mid])
                return mid;
            else if (val < data[mid])
            {
                System.out.print(val+" 介于位置 "+(low+1)+"["+data[low]+"]及中间值 "+(mid+1)+"["+data[mid]+"]，找左半边\n");
                high=mid-1;
            }
            else if(val > data[mid])
            {
                System.out.print(val+" 介于中间值位置 "+(mid+1)+"["+data[mid]+"]及 "+(high+1)+"["+data[high]+"]，找右半边\n");
                low=mid+1;
            }
        }
        return -1;
    }
}

4、斐波那契查找

斐波那契查找要求有序,采用和二分查找/插值查找相似的区间分割策略，仅仅是改变了开始找点的位置，

mid不再是中间或插值得到，而是位于黄金分割点附近，即mid = low+F(k-1)-1。

黄金比例:整体与较大部分的比值为1:0.618 。斐波那契数(黄金分割数列:1,1,2,3,5,8,13,21…)随着此数列的递增，

前后两个数的比例会越来越接近0.618

示例代码:

public class FeiBoNaQi {
    public static void main(String[] args) {
        //待查找序列
        int[] arr = {1,3,5,6,8,13,45,67,133};
        int i = fiboSearch(arr, 133);
        System.out.println("斐波那契查找目标值133在数组中的下标为: "+i);
    }


    //得到一个斐波那契数组
    public static int[] fibonacci(int n) {
        //初始化数组
        int[] fibo = new int[n];

        if (n >= 1) fibo[0] = 1;
        if (n >= 2) fibo[1] = 1;

        for (int i = 2; i < n; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }
        return fibo;
    }
    //主方法

    /**
     * @param arr     待查找序列
     * @param findVal 查找的目标值
     * @return 返回目标值所在的下标
     */
    public static int fiboSearch(int[] arr, int findVal) {
        int low = 0;
        int high = arr.length - 1;
        int k = 0;
        int mid = 0;
        int maxsize = 20;

        //得到斐波那契数组
        int[] fibo = fibonacci(maxsize);

        //判断待查找序列长度应该为哪一个斐波那契数
        while (high > fibo[k] - 1) {
            k++;
        }
        //填充待排序列, 长度为f[k]-1
        //把老数组复制到长度为 f[k]的新数组中
        //超出老数组长度的用0填充
        int[] temp = Arrays.copyOf(arr, fibo[k]-1);
        //填充temp数组中为0的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        System.out.println("填充了最后元素的临时数组: "+Arrays.toString(temp));
        //正式开始查找
        while (low <= high) {
            mid = low + fibo[k - 1] - 1;

            //不断比较不同区间内 findVal 与 temp[mid]的关系
            if( findVal < temp[mid]){
                high = mid -1;
                k -= 1;
            }else if( findVal > temp[mid]){
                low = mid+1;
                k -= 2;
            }else{
                //需要确定返回的是那个下标
                if(mid <= high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/135786.html

赞 (0)
飞熊的头像飞熊bm
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！