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

大家好，欢迎来到IT知识分享网。

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 <= hign){ //定义一个中间值，用于接收数组的中间索引值，因为每回都是从数组的中间开始查找 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)。

运行时间