计算机入门算法——二分查找法

1、引言

笔者对于计算机的研究一直停滞不前，近期想对一些算法进行复习和进一步的研究，每天都会更新一个新的算法，算法有难有易，层层递进。不希望能学的有多么高深，只希望在一些最基本的算法上有编码的思路，或者在一些生产环境中会应用一些算法来解决实际问题。

就比如今天要介绍的第一个查找算法——二分查找法。假设要在电话薄中找一个名字为K大头的人，很习惯的办法就是从头开始翻页，直到进入以K打头的部分。但是这种方法的缺陷就是要逐一查找，时间较长。

于是我们可以有另外一个思路就是每次从中间开始查找，而以K打头的名字就在电话簿中间。再举一个简单的场景，假设登录Facebook时，Facebook会验证是否为自己网站的用户，那就必然要去数据库中作比对，如果逐一对比则用户等待的时间过长，影响用户体验，更合乎逻辑的做法是从中间开始查找，这样就会节约很长的等待时间。

2、二分查找法

二分查找是一种算法，其输入是一个有序的元素列表（注意：列表必须是有序的）。如果要查找的元素包含在列表中，二分查找则返回其位置，否则返回-1。

2.1 二分查找法的原理

举一个示例来讲解二分查找的工作原理。想必大家都玩过1~100的猜数字游戏，目标是以最少的次数猜到这个数字。每次猜测后，会有人告诉你这个数和要找的数是大了还是小了。如果我们从1开始慢慢一个一个数字进行猜测，这样的效率是很慢的，我们通常把这样的查找方式叫做简单查找，更准确的说法是傻找。

猜数字游戏

比较合理的查找方法就是从中间开始查找，如果先猜50的情况下，如果有人给你说大了，那么我们立马排除了后面50个数字，正确答案一定在前面50个数字中，然后我们继续猜测中间的数字，当有人告诉你小了，那么前25个数字也就排除了。一直循环这样下去，你会发现没用几步就可以得出正确答案。这就是二分查找的原理。

二分查找法

2.2 二分查找法的代码实现

在我学习的过程中，我会尽量使用Java语言来编写算法，因为自己接触Java的机会比较多，而且Java语言也比较好用，特此奉上Java实现二分查找法的源代码。

/**

  * 1、二分查找法 适用于有序列表或者数组

  */

 public static int BinarySerach(int[] list, int item){

     //定义一个低位，并赋值数组索引为0

     int low = 0;

     //定义一个高位，并赋值数组索引为数组末尾=数组长度-1

     int hign = list.length - 1;

     /**

      * 开始循环查找         * 查找结束条件为范围缩小到只包含一个元素时返回         */

     while(low

         //定义一个中间值，用于接收数组的中间索引值，因为每回都是从数组的中间开始查找

         int mid = (low + hign) / 2;

         int guess = list[mid];            //如果查询的索引值就为查找到数据，即返回

         if(guess == item){

             //返回中间索引

             return mid;

         }            //如果猜测的数较大，则舍弃后半部分数据，开始在前半部分查找

         /**

          * 此时修改高位为前半部分的末尾索引             */

         if(guess > item){

             hign = mid - 1;

         }

         //如果猜测的数较小，则舍弃前半部分数据，开始在后半部分查找，此时低位索引应修改为后半部分数据

         //的起始索引

         else {

             low = mid + 1;

         }

     }

     //执行循环之后没有查找返回-1

     return -1;

 }

2.3 运行时间

每一种算法都有自己的运行时间，而衡量运行时间的方法通常采用大O表示法。大O表示法是一种比较特殊的表示方法，指出了算法的速度有多快，根据刚才的推演，如果列表中有100个元素，最多只要猜7次就可以查找到正确答案，如果列表中包含40亿个数字，最多需要猜32次。二分查找的运行时间由此称为对数时间（或log时间），用大O表示法表示为O(logn)。

运行时间