[详解C语言]一文带你玩转二分查找-折半查找算法

引入二分查找

本文带着大家学习一个简单的二分查找算法，也叫折半查找算法
先给大家提出一个问题

额，大家应该都会碰到这种情况，那大家怎么猜呢？
我想一定是会说1000，他说太少了，你又猜1500…

这其实就是二分查找的应用。
接下来我们来看一个问题

如何在一个有序数组中查找一个数字？

有一部分帅气的观众可能会说:
直接遍历数组，一个一个对比就找到了啊

但是大家有没有想过一个问题，数组中如果只有几十个数的话，那完全可以这样做
那如果数组中有几十万个呢？
这样遍历绝对是非常消耗时间，题目很明确说有序数组，如果直接遍历，我们是不是对不起有序这二字呢？

分析二分查找

我们用一个简单的实例来实现一下二分查找

比如有这样一个数组

计算中间下标的两种方法

我们在其中查找一个数字。使用二分查找，我们如何确定中间值呢？

有人说，数组长度除以二，但是中间值会变，数组长度不可变 ----排除

这边我们给大家带来两种方法来计算中间值
首先大家要清楚，我们要有两个边界，就是范围，比如鞋子02000变成10002000
我们使用两个下标作为两端，left 以及 right 中间值我们定义为mid

第一种

mid = (left + right) / 2;

我对长度为奇数和偶数的数组都进行了分析，这种方法并没有漏过任何一个数，所以可以使用

第二种

第一种方法有一种弊病，如果数组特别长的话，left+right可能会超出类型的最大值范围
我们得想办法解决掉这个问题

假如我们把left最上边那一小块放到left上边，是不是就是中间值了呢

、
把这种方法写成表达式就是

mid = (right - left) / 2 + left;

这就是两种计算中间下标的方法

代码实现

• 当mid处的值 < 待查找的值的时候 ，需要把 mid处的以及前边的舍弃,即left右移， left = mid +1;
• 当mid处的值 > 待查找的值的时候 ，需要把 mid处的以及后边的舍弃,即right左移，right = mid -1;
• 当相等时，便不再查找。

还有一个问题,什么时候就不再查找了呢？

• left < right 时，中间仍有数据未查找
• left = right 时，有一个数未比较
• left>right 时，都找完了，没找到

所以当left > right 时，就没必要查找了
话不多说，直接上代码

#include<stdio.h>//详解二分查找intmain(){int arr[10]={1,2,3,4,5,6,7,8,9,10};//计算数组长度int length =sizeof(arr)/sizeof(arr[0]);int n =0;//待查找的值scanf("%d",&n);int left =0;//左下标int right = length -1;//右下标int mid =0;//中间下标while(left <= right){
        mid =(left + right)/2;if(arr[mid]> n){
            right = mid -1;}elseif(arr[mid]< n){
            left = mid +1;}else{printf("找到了，下标为%d\n", mid);break;}}if(left > right){printf("找不到，数组中不存在该值\n");}return0;}

总结

• 理解二分查找法的实现方式
• 核心在于中间下标的控制以及下标的变化

大家下来一定要自己画图理解，写代码测试，多写写就悟了。
注:

• 本文所有见解，为本人拙见，如有误导，请多指教
• 如果对您有所帮助