C 说说折半查找（二分法）

学校的一道上机题：

编写程序，在整数数组中设置10个值（例如学生年龄），然后从键盘输入一个要查找的年龄，并输出查找结果。
[提示]可以利用标志变量表示查找的结果。

因为无聊，所以就用了折半查找，上次说【两分法】被鄙视了，所以这真的是二分法啦。

首先二分法需要先排序，排序可以用各种函数，也可以用冒泡排序，以前我写过关于冒泡排序（PHP实现冒泡排序），因此这里对冒泡排序是什么不多做解释，直接上代码。

    for (i = 0; i < NUM; i++)
        for (j = 0; j < NUM - 1 - i; j++) {
            if (ages[j] > ages[j + 1]) {
                temp = ages[j];
                ages[j] = ages[j + 1];
                ages[j + 1] = temp;
            }
        }

这样就排序完了，从小到大。
接着我们就可以开始折半了。
关于这点，以前在猜数字里也写过

    while (low <= high) {
        guess = low + (high - low) / 2;
        if (ages[guess] == searching) {
            result = ages[guess];
            break;
        }
        else if (ages[guess] > searching)
                high = guess - 1;
        else
            low = guess + 1;
    }

上次写的其实是有问题的，因为这样会造成无限逼近而不结束的后果，所以我们采用了+1 以及 -1。

在声明和初始化上：

    int low = 0, high = NUM - 1, guess;

    guess = low + (high - low) / 2;

关于guess = low + (high - low) / 2;，从数学的角度而言和(low + high) / 2并没有什么区别，但实际上计算机是有范围的，后者容易造成溢出，前者把可折半的范围扩大了，所以前者是优良的写法。

那么，源码：

#include <stdio.h>

#define NUM 10

int main(void)
{
    int ages[NUM] = {5, 80, 55, 30, 60, 22, 32, 18, 43, 35};
    int i, j, temp, searching;   /* 循环 */
    int result = -1;
    int low = 0, high = NUM - 1, guess;

    guess = low + (high - low) / 2;

    printf("Please puts the age you want to search: ");
    scanf("%d", &searching);

    /* 冒泡排序 */
    for (i = 0; i < NUM; i++)
        for (j = 0; j < NUM - 1 - i; j++) {
            if (ages[j] > ages[j + 1]) {
                temp = ages[j];
                ages[j] = ages[j + 1];
                ages[j + 1] = temp;
            }
        }

    /* 折半查找 */
    while (low <= high) {
        guess = low + (high - low) / 2;
        if (ages[guess] == searching) {
            result = ages[guess];
            break;
        }
        else if (ages[guess] > searching)
                high = guess - 1;
        else
            low = guess + 1;
    }

    if (result != -1)   /* 如果没有找到对应值 */
        printf("Yes the age your printing is on our database, is it %d ?\n", result);
    else
        printf("Sorry I couldn't find the number your print: %d!\n", searching);

    return 0;
}