4.二分查找

目录

遍历

二分查找

原理演示

代码部分

---

arr[]={1,2,3,4,5,6,7,8,9,10}，如何找到数字7？

遍历

利用for循环，从下标为0的数字开始查找，当循环到第七次时，找到数字7。

当数组中的数字个数不确定时，可以通过sizeof来计算。sizeof（arr）求的是整个数组的大小，sizeof（arr[0]）求的是第一个元素的大小，单位是字节。将前者除以后者，得到数字个数。

//遍历
#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int input = 0;
	scanf("%d", &input);
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < sz; i++)
	{
		if (arr[i] == input)
		{
			printf("找到了，下标为%d\n", i);
			break;
		}
	}
	return 0;
}

利用for循环的遍历似乎可以解决这类问题，但是如果在1~10000中找某个数呢，如果一个一个遍历似乎太浪费时间了，下面介绍二分查找。

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

注意：二分查找使用的前提必须是有序数列！！！
 

原理演示

求元素的下标：利用sizeof，通过sizeof(arr) / sizeof(arr[0])计算元素个数，因为数组的下标是从0开始的，将其结果再减1，即为最后一个元素的下标数。

记录中间数：设定两个变量left、right来锁定我们的下标范围，利用(right-letf)/2来找到中间数。每次范围逐步缩小时，left、right所对应的下标范围也应更新。

初始化：将left下标定为0，right下标定位9。

第一次查找：判断left、righ的中间数与7的大小：5<7，将left移至5+1。

 

第二次查找：判断left、righ的中间数与7的大小：8>7，将right移至8-1处。

 

 

第三次查找：判断left、righ的中间数与7的大小：6<7，将right移至6+1处。

 第四次查找：判断left、righ的中间数与7的大小：7=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]);
	int input = 0;
	scanf("%d", &input);
	int left = 0;
	int right = sz-1;
	int mid = 0;
	while (left <= right)
	{
		mid = left+(right - left) / 2;
		if (arr[mid] < input)
		{
			left = mid + 1;
		}
		else if (arr[mid] > input)
		{
			right = mid - 1;
		}
		else
			break;
	}

	if (arr[mid] == input)
		printf("找到了，下标是%d\n", mid);
	else
		printf("没找到\n");

	return 0;
}

查找过程在函数中：

#include<stdio.h>

void check(int sz,int* arr,int input)//int* arr与int arr[]一致，都是传数组首元素的地址
{
	int left = 0;
	int right = sz - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (arr[mid] < input)
		{
			left = mid + 1;
		}
		else if (arr[mid] > input)
		{
			right = mid - 1;
		}
		else
			break;
	}
	if (arr[mid] == input)
		printf("找到了，下标是%d\n", mid);
	else
		printf("没找到\n");
}

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int input = 0;
	scanf("%d", &input);
	check(sz, arr, input);
	return 0;
}