【c语言练习之二分查找】

二分查找

二分查找的前提

二分查找必须是在一个整形的有序数组中实现

二分查找的思想

对于一个整形的有序数组，输入一个你想要查找的数key，将key与数组的中间元素mid作比较，使得数组被分成2部分，要查找的数key肯定在某一部分，这样就可以舍弃另一部分，在另一部分中继续用这种思想，把剩余数组分成2部分，缩小查找的范围，直至找到key，或者输入的key不在这个数组中，程序结束。

二分查找的实现

下面是在一个整形数组中查找整数key = 7的过程
这是一个升序的整形数组arr[9]={1,2,3,4,5,6,7,8,9};

首先定义数组的左下标为Left = 0，右下标为Right = 8（数组元素个数-1）
中间元素下标 mid = (Left + Right)/2
输入要查找的key

int arr[9] = { 1,2,3,4,5,6,7,8,9 };
	int key = 0;
	scanf("%d", &key);//输入要查找的元素
	int Left = 0;//左下标为0
	int Right = 8;//右下标为数组元素个数-1，即9-1=8
	int mid = 0;//中间元素下标
	mid = (Left + Right) / 2;

第一次循环
Left=0,Right=8
下标mid=（0 +8）/ 2 = 4
我们要找key=7，将可以key与arr[4]=5作比较，发现key > arr[4]=5，所以要查找的数在arr[mid]的右边,所以右下标Right不变，左下标Left=mid+1=5

第二次循环
Left=5,Right=8
下标 mid =（5+8）/ 2 = 6
继续将key=7与arr[6]作比较，发现key==arr[6]，找到了，打印下标mid=6

循环条件
while(Left<=Right)时，进入循环，查找key
如果循环结束，进入下面的if语句中，说明在数组中没找到key

if (Left > Right) {
		printf("很遗憾，不存在您要查找的数");
	}

代码部分

#include<stdio.h>
int main()
{
	int arr[9] = { 1,2,3,4,5,6,7,8,9 };
	int key = 0;
	printf("请输入你要查找的元素:");
	scanf("%d", &key);//输入要查找的元素
	int Left = 0;//左下标为0
	int Right = 8;//右下标为数组元素个数-1，即9-1=8
	int mid = 0;//中间元素下标
	while (Left <= Right)
	{
		mid = (Left + Right) / 2;
		if (key > arr[mid]) {
			Left = mid + 1;
		}
		else if (key < arr[mid]) {
			Right = mid - 1;
		}
		else {
			printf("你要查找的元素下标为:%d\n", mid);
			break;
		}//如果key==arr[mid]，打印下标

	}
	if (Left > Right) {
		printf("很遗憾，不存在您要查找的数");
	}
	return 0;
}

二分查找的好处

如果不使用二分查找，在这样一个数组中，遍历数组，才能找到想要的数字，增加了程序的运行时间。

用遍历数组的方法查找

int main()
{
	int arr[9] = { 1,2,3,4,5,6,7,8,9 };
	int key = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);//求数组元素个数
	scanf("%d", &key);
	//遍历数组
	for (int i = 0; i < sz; i++){
		if (arr[i] == key){
			printf("你要查找的元素下标为:%d\n", i);
		}
	}
	return 0;
}