二分查找

1. 二分查找

在对线性表的操作中,经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。

算法介绍:

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。采用的是分治法。

时间复杂度分析:

时间复杂度无非就是while循环的次数! 总共有n个元素, 渐渐跟下去就是n,n/2,n/4,….n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,(是以2为底,n的对数) 所以时间复杂度可以表示O()=O(log2 n)

public class HalfSearch { 
        private static ArrayList list=new ArrayList(); //创建数组队列
        public static void main(String[] args) {    //主方法
            for(int i=0;i<4;i++)
            {    Scanner Sca =new Scanner(System.in);
         int str=Sca.nextInt();

         int a=Sca.nextInt();
         list.add(a);
            }
            System.out.println("请输入要查找的数:");

                Scanner Sc =new Scanner(System.in);  //输入数组队列

         int b=Sc.nextInt();
         HalfSearch hf=new HalfSearch();
        hf. halfSearch(b,list);   //二分查找
        }

        public void halfSearch (int b,ArrayList list){
            int length=list.size();
            int l=0;
            int m=(length+l)/2;   
            while(l<=length){      
                //b=(int) (list.get(m));
            if(b<((int)list.get(m))){        //小于中间数
             length=length/2; 

            length=m-1;
            }else if (b>(int)list.get(m)){   //大于中间数 
                l=m+1;
                }
                else if(b==(int)list.get(m)){  //等于中间数,输出 
                    System.out.println("数已经找到,位置是:"+m); 
                }
        }
        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏lgp20151222

MySql 模糊查询

SQL模糊查询,使用like比较关键字,加上SQL里的通配符,请参考以下:  1、LIKE'Mc%' 将搜索以字母 Mc 开头的所有字符串(如 McBadden...

971
来自专栏用户画像

7.2.2 插入排序之折半插入排序

注意到该算法中,总是边比较边移动元素,下面将比较和移动操作分离出来,即先折半查找出元素的待插入位置,然后再统一地移动待插入位置后的所有元素。

1091
来自专栏码匠的流水账

聊聊base62与tinyURL

base64大家肯定是很熟悉了,那base62是什么东东,它常被用来做短url的映射。

1512
来自专栏desperate633

LintCode 主元素 III题目分析代码

给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的1/k。 注意事项 数组中只有唯一的主元素

601
来自专栏从流域到海域

Python基本数据类型

其实之前有一篇博客:C\C#\Java\Python 基本数据类型比较 https://cloud.tencent.com/developer/article...

2536
来自专栏大数据钻研

Java 集合框架 HashSet 和 HashMap 源码剖析

总体介绍 之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一...

3066
来自专栏老马说编程

(55) 容器类总结 / 计算机程序的思维逻辑

从38节到54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结: 用法和特点 数据结构和算法 设计思维和模式 用法和特点 我们在52节...

2277
来自专栏dotnet & java

用泛型来实现编译时期的类型推断

第一章都是讲泛型的,距离上一篇Effective C#的随笔已经是很久以前的事情了。。。

853
来自专栏java一日一条

Java 集合框架 HashSet 和 HashMap 源码剖析

之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一个Hash...

872
来自专栏Danny的专栏

HashMap实现原理及源码分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

3.4K3

扫码关注云+社区

领取腾讯云代金券