CodeSky 代码之空

随手记录自己的学习过程

C 说说折半查找(二分法)

2014-05-13 14:40分类: C评论: 0

学校的一道上机题: 编写程序,在整数数组中设置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

评论 (0)