[Java知识库]数组中的查找算法和二分查找算法—Java语言实现

数组中的查找算法和二分查找算法-Java语言实现

前言

以前大二的时候，为了激发学妹们对编程的兴趣，我决定给她们分享一些编程的技能。由于之前给学弟分享过解一元二次方程-Java语言实现，所以要是这次还是给学妹们分享一样的知识，大概会显得我很low吧，我也会因此失去她们的宠幸。

我一直苦苦思索，该给她们分享什么好呢……

突然有个长得很乖的学妹跟我说，想找男朋友。于是我计上心头，干脆我给她们写一个查找算法吧，但是只写一个查找算法怕是无法满足学妹们对知识的渴望，她们对知识的如狼似虎般的心，我是深有体会的……

学妹露出邪魅的一笑对我说，她想快点找到男朋友

我一听就明白了，果然女孩子做什么事都喜欢快一点亦或是更快一点

她这句话给我了灵感，直接查找太慢，我再优化一下，整个二分查找算法不是更快了吗？这样肯定能满足她们了吧

说干就干，于是我便理清思路开始写代码

正文

我跟学妹们解释，在大学里找到合适的男朋友就像是从数组中查找到你要找的数一样

首先，创建一个能存储10个元素的int型数组

int array[]=new int[]{3,6,7,9,10,1,2,4,5,8};

然后输入要查询的数字，再跟数组里的元素进行比较

		int i;
        for (i = 0; i <array.length ; i++) {
            int k=i+1;
            if(key==array[i]) {
                System.out.println("找到了,是第" + k + "个数");
                break;
            }
        }
        if(i==array.length)
            System.out.println("没找到");

如果迭代变量i已经超出了数组的长度，那么输出没找到

下面是完整的代码

public class search {
    public static void main(String[] args) {
        int array[]=new int[]{3,6,7,9,10,1,2,4,5,8};

        System.out.println("请输入你要查找的数: ");

        Scanner sc=new Scanner(System.in);

        int key=sc.nextInt();

        int i;
        for (i = 0; i <array.length ; i++) {
            int k=i+1;
            if(key==array[i]) {
                System.out.println("找到了,是第" + k + "个数");
                break;
            }
        }
        if(i==array.length)
            System.out.println("没找到");
    }
}

二分搜索算法

上面写的最最最垃圾的搜索算法，无脑+暴力

下面我们来写有技术含量的折半查找

这次我们需要创建的是一个按照升序排列的数组

int array[]=new int[]{1,2,3,4,5,6,7,8,9,10};

然后定义几个变量

		int key;//key是要查找的数
 		int low=0;//low是数组的第一个元素的下标
        int high=array.length-1;//high是数组最后一个元素的下标
        int middle;//middle是数组中间的元素的下标

现在正式开始查找

 while(high>=low) {

           middle=(low+high)/2;

            if(array[middle]<key){
                low=middle+1;
            }
            else if (array[middle]>key){
                high=middle-1;
            }

            else {
                System.out.println("你要查找的数在第"+(middle+1)+"个");
                break;
            }
        }
       if(low > high)
           System.out.println("找不到");

如果查找的数是6，那么如下面的图所示

折半查找，就是不停的对半查找，直到找到为止

要是low的值大于了high的值，说明这整个数组已经遍历完了，但是还是没有找到我们要查找的数，所以只能输出找不到

完整代码如下：

public class search2 {
    public static void main(String[] args) {
        int array[]=new int[]{1,2,3,4,5,6,7,8,9,10};

        System.out.println("请输入你要查找的数: ");

        Scanner scanner = new Scanner(System.in);

        int key=scanner.nextInt();

        int low=0;
        int high=array.length-1;
        int middle;

       while(high>=low) {

           middle=(low+high)/2;

            if(array[middle]<key){
                low=middle+1;
            }
            else if (array[middle]>key){
                high=middle-1;
            }

            else {
                System.out.println("你要查找的数在第"+(middle+1)+"个");
                break;
            }
        }
       if(low > high)
           System.out.println("找不到");
    }
}

总结

我们能很清楚的知道，暴力查找算法的时间复杂度是O(n)

而折半查找算法的时间复杂度为O（$lo{g}_{2}n$）

所以当数组中的元素越多时，折半查找所展示出来的算法优越性就越好

后续

于是我终于满足了学妹们，她们对折半查找非常满意，毕竟这能让她们更快的找到男朋友

然后，结果是……

终究是错付了，学妹又被辜负了，我为什么要说又？

今天的分享就到这里，我们下期见~

本文章选自微信公众号onceCode
如果大家喜欢喜欢的话欢迎关注公众号
附上微信公众号链接