企业官网建设流程全解析

为什么二分查找每比较一次就能砍掉一半数据？很多人第一步就写错了

如果 100 万个数字让你找一个，你会一个一个找吗？

很多刚学 C 语言的人，第一反应都是写一个for循环，从第一个元素开始一直往后比。如果目标刚好在最后一个位置，那就意味着要比较 100 万次。

有没有更快的方法？有，而且几乎所有程序员都会用——二分查找（Binary Search）。

它最神奇的地方在于：每比较一次，就直接排除掉一半的数据。

今天我们就把二分查找真正讲明白，以及最容易踩坑的几个地方。

① 为什么普通查找这么慢

错误示例

最容易想到的方法，就是顺序查找：

intarr[]={3,5,7,9,12,18,20};for(inti=0;i<7;i++){if(arr[i]==12){printf("%d",i);break;}}

如果目标在最后一个位置，程序就得从头比到尾——第 1 次、第 2 次、第 3 次……直到第 7 次才找到。100 万个数据，最坏情况要比较100 万次。

为什么错

顺序查找不会利用任何已有的信息。即使数组已经排好序，它依然傻傻地从头开始一个个比。

正确思路

如果数组已经有序，我们完全可以利用大小关系，一次排除掉一半数据。这就是二分查找的出发点。

一句总结：顺序查找不利用顺序，因此效率最低。

② 二分查找为什么这么快

假设数组已经升序排列：

1 3 5 7 9 11 13 15 17

目标是11。

第一步，取中间元素：1 3 5 7 [9] 11 13 15 17

11 > 9，说明目标在 9 的右边，左边全部丢掉。剩下：

11 13 15 17

第二步，再取中间：11 [13] 15 17

11 < 13，说明目标在 13 的左边，右边全部丢掉。剩下：

11

第三步，找到11。

你看，只比较了三次。每一步都把数据量减半，这就是二分查找快的原因。

正确代码

while(b<=e){mid=(b+e)/2;if(arr[mid]==key)break;if(arr[mid]>key)e=mid-1;elseb=mid+1;}

二分查找的时间复杂度是 O(logN)。100 万个数据，大约 20 次比较就能找到，和 100 万次比是天壤之别。

一句总结：二分查找快，不是因为比较本身快，而是因为每次都减少一半搜索范围。

③ 为什么数组必须有序

这是二分查找最重要的前提。

错误示例

intarr[]={9,2,15,7,1,20};

对这个无序数组直接做二分查找。

为什么不行

拿它来走一次：中间元素是15，要找的是7。看到7 < 15，你敢把右边全部丢掉吗？当然不敢——因为数组是无序的，7可能在任何位置。

二分查找依赖的前提是：左边都比中间小，右边都比中间大。只有这样才能安全地舍弃一半数据。数组无序时，这个条件不成立。

正确做法

intarr[]={1,2,7,9,15,20};// 先排序再用二分查找

一句总结：数组无序，就不能用二分查找。

④ 为什么b <= e很多人写错

错误示例

while(b<e)

为什么错

当b == e时，搜索区间其实还剩下最后一个数字，仍然需要比较一次。如果写成b < e，循环直接结束，最后一个元素永远不会被检查。

比如数组{5}只有一个元素，b = 0，e = 0。这时候b < e不成立，循环直接跳过，目标就在眼前却永远找不到。

正确代码

while(b<=e)// b == e 时还要检查一次

一句总结：b <= e表示最后一个元素也要检查。

⑤ 为什么mid的计算也有讲究

很多教材都这样写：

mid=(b+e)/2;

对于一般练习，这样足够了。但有一个潜在风险——整数溢出。

当b和e都很大时（比如接近INT_MAX），b + e可能超过int的表示范围，结果变成负数，然后mid就变成负的了。

工程开发中更推荐这样写：

mid=b+(e-b)/2;

结果和(b+e)/2完全一样，但永远不会溢出。

一句总结：工程中推荐用b + (e - b) / 2避免溢出。

⑥ 查找失败怎么判断

错误示例

while(b<=e){// ...}printf("找到了");

循环结束后直接认为找到了。

为什么错

循环正常结束有两种可能：一是找到了，用break跳出来的；二是b > e了，说明整个数组都搜完了也没找到。如果不区分这两种情况，就会"强行找到"。

正确代码

intpos=-1;while(b<=e){mid=b+(e-b)/2;if(arr[mid]==key){pos=mid;break;}if(arr[mid]>key)e=mid-1;elseb=mid+1;}if(pos==-1)printf("未找到\n");elseprintf("找到，下标 = %d\n",pos);

一句总结：二分查找结束后，没命中目标就是查找失败。

完整示例

把上面所有要点串起来，一个完整的二分查找程序：

#include<stdio.h>intmain(){intarr[]={1,3,5,7,9,11,13,15,17};intkey=11;intb=0;inte=8;intpos=-1;while(b<=e){intmid=b+(e-b)/2;if(arr[mid]==key){pos=mid;break;}if(arr[mid]>key)e=mid-1;elseb=mid+1;}if(pos==-1)printf("未找到\n");elseprintf("找到，下标 = %d\n",pos);return0;}

时间复杂度

数据量越大，二分查找的优势越明显。100 万数据 vs 20 次比较，差距就是这么大。

每日一练

已知一个升序数组：

intarr[]={2,4,6,8,10,12,14,16,18,20};

请编写一个二分查找函数：

intBinarySearch(intarr[],intn,intkey);

要求：

• 找到返回元素下标
• 找不到返回-1
• 使用b、e、mid三个变量
• 循环条件用b <= e
• 用b + (e - b) / 2计算中间位置

intBinarySearch(intarr[],intn,intkey){intb=0;inte=n-1;while(b<=e){intmid=b+(e-b)/2;if(arr[mid]==key)returnmid;if(arr[mid]>key)e=mid-1;elseb=mid+1;}return-1;}

今日避坑指南

1. 二分查找只能用于有序数组——无序的话先排序，或者用别的查找方式。
2. 搜索区间是b = 0，e = n - 1——下标从 0 开始，最后一个元素的下标是n - 1，不是n。
3. 循环条件必须写b <= e——b == e时还有一个元素要比较，写成<会漏掉它。
4. arr[mid] > key时搜左半区——e = mid - 1，不是e = mid。同理，b = mid + 1。
5. 用b + (e - b) / 2代替(b + e) / 2——避免索引非常大时的整数溢出。
6. 查找失败要返回 -1——不要默认一定找得到，别忘了处理找不到的情况。

专题总结

二分查找的代码不长，但每一步都是细节：边界要不要等号？区间怎么缩？找不到怎么办？把这些细节吃透了，二分查找就是个很趁手的工具。

上一篇：为什么冒泡排序这么慢？一篇讲透 C 语言三种经典排序算法