前言

当我们想知道在一组数集合中是否存在一个数时，可以用循环从1开始遍历，遇到时则输出。但是，如果举个实际的生活中的例子：我买了个新手机，价格不到3000，让你猜价格，你会从1开始猜吗？ “1块？一块不对…两块？两块不对…”——这显然是不够现实的。

我想正常人都应该有种思路：先猜大点，大了，那就再说小点，又小了，那再猜大点吧……

不到3000的鞋子对吧，行。 1500？ 小了  2500？ 大了  2000？……

那么思路应该是从1-3000中找一个数【每次猜中间数】

这才正常吧

直男思想：要从有序数组中找有没有7对吧，行！我用for循环从1开始遍历，一个一个找，肯定可以吧。

int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int x = 7;
    int i = 0;
    for (i = 0; i < 10; i++)
    {
        if (arr[i] == x) {
            printf("找到");
            break;
        }
    }
    return 0;
}

看着其实没问题对吧，但这数字要是大了呢，要是给你整个上千上万呢？

这时二分查找（折半查找）就来了

首先需要说的是，使用 二分查找 是有


前提


的，要求必须是在

有序数列并且顺序存储

（数组）

二分查找的思路


：1.确定被查找范围的左右下标，

left

和

right

。

2.根据下标

left

和

right

确定中间元素的下标

mid。

3.根据

mid

锁定的元素和需要查找的元素进行比较，从而确定新的查找范围.（新

left

和

right

）

比如说需要在数组arr中找到数字7，也就是下标6：

确定left和right后已知现在范围为0~9，通过mid和所查找数（7）的下标（6）进行比较，不断缩小范围。第一遍mid为4小于6，所以让left往右走至mid+1为5，从而重新确定范围为5~9。再重新计算mid为7又大于6了，所以让右边的right往左走至mid-1为6，此时范围是5~6。最后再进行一次比较mid为5小于6，所以让left往右走至mid+1为6，最终确定了left = right = 6，也就是找到了整型7的下标。

最后，用代码实现为：

#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算arr数组的长度，用以直到下标right的值
	int left = 0;
	int right = sz - 1;
	int k = 7;  //数组中找到整型7 可使用scanf("%d",&k);改变查找数
	int flag = 0;  //设置标志
	while (left <= right)
	{
		int mid = (left + right) / 2;  //此语句必须在while循环内，因为mid是不断变化的
		if (arr[mid] == k)   //比较下标mid对应的值与所查找数的值
		{
			printf("找到了，下标为%d",mid);
			flag = 1;  //若找到改变标志
			break; //跳出while循环
		}
		else if (arr[mid] < k)
			left = mid + 1;
		else 
			right = mid - 1;
	}
	if (flag == 0)  //此时若找到，则flag为1不读取此语句
		printf("没找到");
	return 0;
}

此处有三个地方需要注意

第一：

初始化right时，right的取值应为sz – 1，因为下标是从0开始的，sz存储的是数组arr的长度。

int sz = sizeof(arr)/sizeof(arr[0])

用arr数组所占内存的总大小除于arr数组中单个元素的大小，即为长度。

第二：

flag的设定是为了设计标志：falg初始化为零，当查找到数组中的元素7后，改变flag

为1，在跳出循环，此时后面的if条件语句判断为假，不执行。但当未找到7，flag依旧为0，if条件为真，输出没找到。

int flag = 0;

第三：

mid锁定的元素与7进行比较时不可能只比较一次，所以需要用循环，此处适合使用while循环。

if (arr[mid] == k)
{
	printf("找到了，下标为%d",mid);
	flag = 1; 
	break;
}
else if (arr[mid] < k)
	left = mid + 1;
else 
	right = mid - 1;

注意while循环的条件是

while (left<=right)

因为在不断比较和移动下标确定范围时，范围不断缩小，但不可能交叉，范围应该是最终确定在一个数上。

那么今天的分享就到这里了，谢谢大家，如果觉得不错的话还请给个关注哈！

新手上路，如若有错误请大神提出！