数组练习之：二分查找法

概要

? ?给定一组有序（递增或递减）的数据，如{1,2,3,4,5,6,7，8,9,10}如果我们想要查找其中的某个数字，首先想到的一定是挨个遍历，一个个进行核对，但对于这种特殊的数据组合，用这种方法显然耗时费力，效率不高。这时就要用到“二分查找法”了。

??

技术名词解释

何为“二分查找法”

我举个例子大家就明白了，假设我们要查找的数字是7，首先将有序数据储存到一维数组中，如下：

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

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

? ?我们先将下标0和9相加再除以2，得到“中间下标”4，下标4对应的“中间元素”值就是5，5很显然比7小，由于此系列数据是递增的，因此我们可以知道目标值7在“中间元素”的右边，此时我们就可以摒弃5以及5左边的数字了，接下来在6-10之间查找即可，再采用刚才的方法，将下标6和9相加除2得出新的“中间下标”7，对应数字是8，8比7大，所以7在8的左边，摒弃8以及8右边的数，进一步缩小了范围，此时只剩下5和7，继续求两者下标的平均值，得5（对应6），还是比7小，再次排除5，那么现在就只剩下7了，根据刚才的流程，首尾下标均为6，平均值为6，而下标6对应的数字就是7，所以我们就找到了7.

? 综上，我们只查找了4次就得到了结果，如果挨个去找，得需要七次查找才能结束，效率孰高孰低显而易见。

整体架构流程

接下来我们看一段代码：

#include <stdio.h>

int main()
{
	char arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	int key = 7;//要查的数字
	int mid = 0;//中间下标

	while (left <= right)
	{
		mid = (left+right)/2;
		if (arr[mid] > key)
			right=mid-1;
		else if (arr[mid] < key)
			left=mid+1;
		else
		{
			printf("找到了，下标是%d\n", mid);
			break;
		}
	}
	if (left > right)
		printf("没找到.\n");
	return 0;
}

? ?二分查找时，求中间下标是很重要的一步，它是由每次我们要查找的范围首尾下标的平均值确定的，因此我们设出left作为左下标（首），right作为右下标（尾），mid作为中间下标，用（left+right）/2表示，左右下标不是固定不变的，如果arr【mid】<key(目标数字),那么就“弃左留右”，右下标不变，左下标变为mid+1，arr[mid]>key则右下标变为mid-1，再进行下一轮二分查找，由此可见循环是必不可少的，仔细想想，不难发现每次查找后我们的查找范围就会缩小一半，但不论如何，left始终小于等于right，找到之前left一定小于等于right，如果找不到，left就会大于right（如果数据里没有目标值，那最后一定会锁定到一个数字，左右下标也都是此数的下标，如果key大于此数，则左下标+1，若key小于此数，则右下标-1，最终都是left<right）。因此循环条件是left<=right;循环时如果找到key，则打破循环。如果是因为left>right导致循环结束，那就是没找到key。

技术细节

提示：这里可以添加技术细节

由于我们没有规定数组大小，所以右下标的初始化应由sizeof(arr)/sizeof(a[0])-1得出

小结

当遇到一组有序的数据组合，我们要查找某个数时，不建议采用顺序查找，因为效率低。

采用二分查找法是针对此特殊情况的不二门选。