数组练习(2)二分查找

题目:二分查找，又叫折半查找。就是在一个升序的数组中查找指定数字n

有序的数据才能使用折半查找

int main()
{
	int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
	int k = 0;
	scanf("%d", &k);
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		if (arr[i] == k)
		{
			printf("找到了，下标是%d\n", i);
			break;
		}
	}
		if (i == sz)
		{
			printf("找不到\n");
		}
	
		return 0;
	}

当然，对代码进行优化

分析：有一组数组? ?1? 2? 3? 4? 5? 6? 7? 8? 9? 10

? ? ? ? ? ? ? ? ? ? ? 下标? ?0? 1? 2? 3? 4? 5? 6? 7? 8? ?9

如果我们求的数k = 7，那么下标的范围是0~9，（0+9）/ 2 =4，而下标是4的数字是5，以此锁定k在5~9，（5+9）/2 = 7，7对应的数字是8，因此锁定5~6，（5+6）/2 = 5，下标5对应的数字是6，在5~6范围中比5大，只能是6，而下标是6所对应的数字是7，就是我们要找的数字。

?下标范围? ? ? ? ?中间下标? ? ? ? ? ? 对应是数值? ? ? ? ? ?目标数值

0~9? ? ? ? ? ? ? ? ? ?4? ? ? ? ? ? ? ? ? ? ? ? 5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?7

5~9? ? ? ? ? ? ? ? ? 7? ? ? ? ? ? ? ? ? ? ? ? ?8? ? ? ? ? ? ? ? ? ? ? ? ? ? ???7

5~6? ? ? ? ? ? ? ? ? 5? ? ? ? ? ? ? ? ? ? ? ? ?6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?7

6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?7

一次折半过程：

1.确定被查找的范围

2.确定被查找范围的左右下标

3.根据左右下标确定中间元素的下标

4.然后找到中间元素和要找的元素比较

（1）找到了，就结束

（2）找不到，根据大小关系，确定新的查找范围（折半）

int main()
{
	int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
	int k = 0;
	scanf("%d", &k);
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;
	int flag = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] == k)
		{
			printf("找到了，下标是%d\n", mid);
			flag = 1;
			break;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	if (flag == 0)
	{
		printf("找不到");
	}
	return 0;
}