数据结构--二分查找法

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、二分查找法是什么？
• 二、代码实现
• • 1.确立左右下标和中间值下标
  • 2.实现第一次二分查找
  • 3.实现重复循环二分查找
  • 4.目标值不在有序数据范围内
• 完整代码
• 运行效果

---

前言

在面对数据量比较大的有序数据时，要查找到目标值，只是简单的从头开始一个个找，这样需要查找N次,效率十分低下，这使得人很头疼，这时候主角二分查找法登场，我们通过二分查找法只需要查找log2(n)次，大大提高查找效率。

---

``

一、二分查找法是什么？

面对数据量较大的有序数据，我们需要先确定有序数据的中间值，与中间值对比，比中间值大则去除比中间值小的数据，比中间值小则去除比中间值大的数据，重复此步骤直至查找到目标值。
例如
一组有序的数据

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

例如我们需要查找目标值 7，对应数组下标6

这组数据的中间值是5，对应数组下标是4 在经过第一次二分查找法 变成如下
目标值比中间值大，保留比中间值大的数据

第二次二分查找，确立中间值是8 目标值比中间值小，去左边

第三次查找，中间值为7与目标值相同，算法结束。在二分查找法中 我们需要确定数组最左和最右的下标，中间值下标取最左和最右的下标的平均值的整数，中间值下标对应的中间值与目标值对比，不能将数据和数据下标混淆。

二、代码实现 1.确立左右下标和中间值下标

int left = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int right = sz - 1;
	printf("请输入要查找的值:>")；
	scanf("%d",&k)

2.实现第一次二分查找

int mid = (left + right) / 2;//还有一种表达：int mid=left+(right-left)/2;
		if (arr[mid]<k)
		{
			left = mid + 1;
		}
		else if (arr[mid]>k)
		{
			right = mid - 1;
		}
		else
		{
			printf("目标值的下标:%d\n", mid);
			break;
		}

3.实现重复循环二分查找

只需要当left和right之间还有数据时，即left<=right,就会一直不断查找直至找到目标。

	while (left<=right)
	{	
		int mid = (left + right) / 2;//还有一种表达：int mid=left+(right-left)/2;
		if (arr[mid]<k)
		{
			left = mid + 1;
		}
		else if (arr[mid]>k)
		{
			right = mid - 1;
		}
		else
		{
			printf("目标值的下标:%d\n", mid);
			break;
		}
	}

4.目标值不在有序数据范围内

if (left>right)
	{
		printf("要查找的数不在数据范围内\n");
	}

---

完整代码

int main()
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8,  9, 10 };
	int left = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int right = sz - 1;
	int k;
	printf("请输入要查找的值:>");
	scanf("%d",&k);//要查找到的值
	
	while (left<=right)
	{	
		int mid = (left + right) / 2;//还有一种表达：int mid=left+(right-left)/2;
		if (arr[mid]<k)
		{
			left = mid + 1;
		}
		else if (arr[mid]>k)
		{
			right = mid - 1;
		}
		else
		{
			printf("目标值的下标:%d\n", mid);
			break;
		}
	}
	if (left>right)
	{
		printf("要查找的数找不到\n");
	}
	return 0;
}

运行效果