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
评论 (0)