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>
//详解二分查找
int main()
{
	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;
		}
		else if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下标为%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到，数组中不存在该值\n");
	}
	return 0;
}

总结

理解二分查找法的实现方式

核心在于中间下标的控制以及下标的变化

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