二分查找（数组的练习）

一、什么是二分查找

        二分查找（又叫折半查找）是一种查找算法，它能使查找的速度更快，但要求查找的序列必须有序。

        如果我们按顺序在一个序列中查找一个数，当这个数在靠前的位置，查找的速度还好；那么当这个数在很靠后的位置呢？甚至是一个很长的数组，要查找的数是最后一个元素，这种情况下查找的速度就很慢了。因此我们需要用更优的二分查找算法。

二、算法思想

2.1、概述       

        记录数组的三个位置：low、high、mid分别记录当前查找的数组子集的起始位置、结束位置、中间位置。当前数组子集的mid = (low + high) / 2，注意：C语言中整型数相除，结果会舍去小数部分。

        每次将要查找的数key与mid位置的数比较：如果key大于mid位置的数，说明key是在数组右半子集的范围里，那么更新子集的范围，low更新为mid+1；如果key小于mid位置的数，说明key是在数组左半子集的范围里，那么更新子集的范围，high更新为mid - 1。

        重复上述的过程，直到查找到key，或者low大于high（key没在数组中）结束。

2.2、举例

        有序数组如下，并标记三个位置：

（1）查找3（数组里面存在的数）

        第一趟：3比5小

        第二趟：3比2大

        第三趟：3等于mid位置的数3，查找成功。

（2）查找12（数组里面不存在的数）

        第一趟：12比5大

        第二趟：12比8大

        第三趟：12比9大

        第四趟：12比10大

        low比high大，结束，查找失败。

三、代码实现

        代码中使用sizeof计算len的方法，不懂的看这篇文章：http://t.csdnimg.cn/wt5LY；不懂while里EOF用法的看这篇文章的“scanf的返回值”部分：http://t.csdnimg.cn/80wMT。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {

	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int len = sizeof(arr) / sizeof(arr[0]); //数组的长度
	int low, high, mid, key;

	while(scanf("%d", &key) != EOF){ // 控制查找多次
		low = 0;
		high = len - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (key > arr[mid])
				low = mid + 1;
			else if (key < arr[mid])
				high = mid - 1;
			else {
				printf("查找成功，在下标%d处\n", mid);
				break;
			}
		}
		if (low > high)
			printf("查找失败\n");
	}

	return 0;
}

       运行结果：

四、计算mid公式的优化

        当数组很长时，low、high很可能是一个很大的数，这时候会出现一些问题。用Everthing软件查看一下<limits.h>头文件里的INT_MAX的值为2147483647，假如把low和high都赋值为2147483646，看看有什么结果：

         会发现结果跟我们预期的不一样，这是因为数值超过了int类型的长度，发生了溢出（暂且不深入了解是什么原理）。所以需要优化mid的计算方法，如下图所示：

        我们可以把长的与短的做差，再将这个差除以2，最后将这一半补到短的上面，就可以避免加法造成溢出了。因此可以将mid计算公式优化为mid = low + (high - low) / 2。再运行看看：

        得到了正确的结果。

        有人会想，为什么不直接用mid = low / 2 + high / 2呢？因为整除是会舍去小数部分的，两次分别做除法，舍去的小数部分可能更多，误差就更大了。比如3 / 2 + 5 / 2 = 3 ；而(3 + 5) / 2 = 4，两者结果并不一样。