【C语言】算法：二分查找

当我们想在一个有序的序列里面查找一个数字的时候，通常会想到使用循环遍历，也就是下面这种方法：
比如我们想在下面的数组里面找到7：
在这里插入图片描述

int main()
{
	int num = 7;
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };

	for (int i = 0; i < sizeof(arr) - 1; i++)
	{
		if (num == arr[i])
		{
			printf("找到%d了,下标是%d\n", num, i);
			break;
		}
	}

	return 0;
}

如果这个序列没有很大，那这种遍历的方法可以，但设想一下，如果有100,1000或者10000个数字呢，这个时候遍历每个元素显然效率不够高，所以接下来给大家介绍一个方法，叫做二分查找。

什么是二分查找呢，假如我们进行一个猜数字的游戏，范围是1-10之间，根据每次猜的数来反馈告诉你是大了还是小了，那么我们第一次就会猜5，如果小了，那么就在6-10的范围里再猜，如果大了，那就在1-4的范围里猜，这就叫做二分查找，也叫折半查找。

那如何使用C语言的代码来实现二分查找呢，我们来捋一下思路：
这时第一次查找，我们定义一个left指向最左边下标的元素，定义一个right指向最右边的元素，而中间的元素就是left + right / 2，所以指向的是第下标为4的元素。
在这里插入图片描述
这时会发现，mid指向的元素和我们要找的7还是不同，所以我们把left右移，要找6-10之间的元素。

然后第三次再找发现比我们要找的元素大，这时就把right左移，使right = mid - 1，大概思路了解后接下来我们来实现代码：

int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int num = 0;
	//输入要查找的数字
	scanf("%d", &num);

	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	
	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (arr[mid] < num)
		{
			left = mid + 1;
		}
		else if (arr[mid] > num)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到%d了，下标为%d\n", num, mid);
			break;
		}
	}
	//到这里left和right已经错过去了，代表没有要找的元素
	if (left > right)
	{
		printf("没找到");
	}

	return 0;
}