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

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

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

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

1    for (i = 0; i < NUM; i++)
2        for (j = 0; j < NUM - 1 - i; j++) {
3            if (ages[j] > ages[j + 1]) {
4                temp = ages[j];
5                ages[j] = ages[j + 1];
6                ages[j + 1] = temp;
7            }
8        }
9

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

1    while (low <= high) {
2        guess = low + (high - low) / 2;
3        if (ages[guess] == searching) {
4            result = ages[guess];
5            break;
6        }
7        else if (ages[guess] > searching)
8                high = guess - 1;
9        else
10            low = guess + 1;
11    }
12

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

在声明和初始化上：

1    int low = 0, high = NUM - 1, guess;
2
3    guess = low + (high - low) / 2;
4

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

那么，源码：

1#include <stdio.h>
2
3#define NUM 10
4
5int main(void)
6{
7    int ages[NUM] = {5, 80, 55, 30, 60, 22, 32, 18, 43, 35};
8    int i, j, temp, searching;   /* 循环 */
9    int result = -1;
10    int low = 0, high = NUM - 1, guess;
11
12    guess = low + (high - low) / 2;
13
14    printf("Please puts the age you want to search: ");
15    scanf("%d", &searching);
16
17    /* 冒泡排序 */
18    for (i = 0; i < NUM; i++)
19        for (j = 0; j < NUM - 1 - i; j++) {
20            if (ages[j] > ages[j + 1]) {
21                temp = ages[j];
22                ages[j] = ages[j + 1];
23                ages[j + 1] = temp;
24            }
25        }
26
27    /* 折半查找 */
28    while (low <= high) {
29        guess = low + (high - low) / 2;
30        if (ages[guess] == searching) {
31            result = ages[guess];
32            break;
33        }
34        else if (ages[guess] > searching)
35                high = guess - 1;
36        else
37            low = guess + 1;
38    }
39
40    if (result != -1)   /* 如果没有找到对应值 */
41        printf("Yes the age your printing is on our database, is it %d ?\n", result);
42    else
43        printf("Sorry I couldn't find the number your print: %d!\n", searching);
44
45    return 0;
46}
47

CodeSky 代码之空

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

评论 (0)