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

为什么二分查找每比较一次就能砍掉一半数据很多人第一步就写错了如果 100 万个数字让你找一个你会一个一个找吗很多刚学 C 语言的人第一反应都是写一个for循环从第一个元素开始一直往后比。如果目标刚好在最后一个位置那就意味着要比较 100 万次。有没有更快的方法有而且几乎所有程序员都会用——二分查找Binary Search。它最神奇的地方在于每比较一次就直接排除掉一半的数据。今天我们就把二分查找真正讲明白以及最容易踩坑的几个地方。① 为什么普通查找这么慢错误示例最容易想到的方法就是顺序查找intarr[]{3,5,7,9,12,18,20};for(inti0;i7;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 1711 9说明目标在 9 的右边左边全部丢掉。剩下11 13 15 17第二步再取中间11 [13] 15 1711 13说明目标在 13 的左边右边全部丢掉。剩下11第三步找到11。你看只比较了三次。每一步都把数据量减半这就是二分查找快的原因。正确代码while(be){mid(be)/2;if(arr[mid]key)break;if(arr[mid]key)emid-1;elsebmid1;}二分查找的时间复杂度是 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(be)为什么错当b e时搜索区间其实还剩下最后一个数字仍然需要比较一次。如果写成b e循环直接结束最后一个元素永远不会被检查。比如数组{5}只有一个元素b 0e 0。这时候b e不成立循环直接跳过目标就在眼前却永远找不到。正确代码while(be)// b e 时还要检查一次一句总结b e表示最后一个元素也要检查。⑤ 为什么mid的计算也有讲究很多教材都这样写mid(be)/2;对于一般练习这样足够了。但有一个潜在风险——整数溢出。当b和e都很大时比如接近INT_MAXb e可能超过int的表示范围结果变成负数然后mid就变成负的了。工程开发中更推荐这样写midb(e-b)/2;结果和(be)/2完全一样但永远不会溢出。一句总结工程中推荐用b (e - b) / 2避免溢出。⑥ 查找失败怎么判断错误示例while(be){// ...}printf(找到了);循环结束后直接认为找到了。为什么错循环正常结束有两种可能一是找到了用break跳出来的二是b e了说明整个数组都搜完了也没找到。如果不区分这两种情况就会强行找到。正确代码intpos-1;while(be){midb(e-b)/2;if(arr[mid]key){posmid;break;}if(arr[mid]key)emid-1;elsebmid1;}if(pos-1)printf(未找到\n);elseprintf(找到下标 %d\n,pos);一句总结二分查找结束后没命中目标就是查找失败。完整示例把上面所有要点串起来一个完整的二分查找程序#includestdio.hintmain(){intarr[]{1,3,5,7,9,11,13,15,17};intkey11;intb0;inte8;intpos-1;while(be){intmidb(e-b)/2;if(arr[mid]key){posmid;break;}if(arr[mid]key)emid-1;elsebmid1;}if(pos-1)printf(未找到\n);elseprintf(找到下标 %d\n,pos);return0;}时间复杂度情况时间复杂度说明最好情况O(1)一次就命中中间元素最坏情况O(logN)一直缩到只剩一个元素数据量越大二分查找的优势越明显。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){intb0;inten-1;while(be){intmidb(e-b)/2;if(arr[mid]key)returnmid;if(arr[mid]key)emid-1;elsebmid1;}return-1;}今日避坑指南二分查找只能用于有序数组——无序的话先排序或者用别的查找方式。搜索区间是b 0e n - 1——下标从 0 开始最后一个元素的下标是n - 1不是n。循环条件必须写b e——b e时还有一个元素要比较写成会漏掉它。arr[mid] key时搜左半区——e mid - 1不是e mid。同理b mid 1。用b (e - b) / 2代替(b e) / 2——避免索引非常大时的整数溢出。查找失败要返回 -1——不要默认一定找得到别忘了处理找不到的情况。专题总结二分查找的代码不长但每一步都是细节边界要不要等号区间怎么缩找不到怎么办把这些细节吃透了二分查找就是个很趁手的工具。上一篇为什么冒泡排序这么慢一篇讲透 C 语言三种经典排序算法