下载掌阅APP，畅读海量书库
立即打开
对于有序数组，可以采用更高效的二分查找策略。假设要在图1-10所示的数组中查找数字6。
图1-10
首先，将所需查找的数字6和数组正中间位置的元素5进行比较，如图1-11所示。
图1-11
由于6大于5，因此5及其左边的数字均不需要再考虑，可以将查找范围缩减一半，如图1-12所示。
图1-12
继续将所需查找的数字6和剩余元素中正中间位置的8进行比较，如图1-13所示。
图1-13
由于8大于6，因此8及其右边的数字均不需要再考虑，如图1-14所示。
图1-14
继续和剩余元素中正中间位置的6进行比较，发现6即为所查数字，查找结束，如图1-15所示。
图1-15
假设有序数组nums中存储了 n 个数字，变量key存储要查找的数字。二分查找算法比较key和数组nums正中间位置的元素值，如果key更大，则只需在数组nums右边一半的元素中查找；如果key更小，则只需在数组nums左边一半的元素中查找。重复执行上述逻辑，即可很快查找到目标。二分查找算法的伪代码如下。
1 low = 0 2 high = n - 1 3 while low <= high 4 mid = (low + high)/2 5 if key == nums[mid] 6 查找成功，跳出循环 7 if key < nums[mid] 8 high = mid - 1 9 if key > nums[mid] 10 low = mid + 1 11 if low > high 12 查找失败
二分查找算法的完整代码如1-3-1.cpp所示。
1-3-1.cpp
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <conio.h>
4 #include <time.h>
5
6 int main() // 主函数
7 {
8 srand((unsigned)time(NULL)); // 初始化随机种子
9 int nums[100]; // 数组存储多个数字
10 int i;
11
12 // 数组元素初始化为1到100
13 for (i = 0; i < 100; i++)
14 nums[i] = 1 + i;
15
16 printf("有序数组为：");
17 for (i = 0; i < 100; i++)
18 printf("%4d", nums[i]);
19 printf("\n");
20
21 // 生成要查找的数字，为1到100之间的随机整数
22 int key = 1 + rand() % 100;
23 int searchNum = 0; // 查找的次数
24 // 定义变量：查找区域的下边界、上边界、正中间
25 int low = 0, high = 100 - 1, mid;
26
27 // 以下进行二分查找
28 while (low <= high)
29 {
30 searchNum++; // 查找次数加1
31 mid = (low + high) / 2; // 正中间元素的序号
32 if (key == nums[mid]) // 找到了
33 {
34 printf("%d：查找到了，%d是要查找的数字\n", searchNum, nums[mid]);
35 break; // 跳出while循环语句
36 }
37 else
38 {
39 printf("%d：%d不是要查找的数字\n", searchNum, nums[mid]);
40 // 更新查找区域，变成上一步的一半
41 if (key < nums[mid]) // 下一次查找较小的一半数组
42 high = mid - 1;
43 else // 下一次查找较大的一半数组
44 low = mid + 1;
45 }
46 }
47 if (low > high) // 没有找到要查找的数字
48 printf("没有找到要查找的数字%d\n", key);
49 _getch();
50 return 0;
51 }
1-3-1.cpp的运行效果如图1-16所示。
图1-16
将1-2-2.cpp和1-3-1.cpp结合，即可实现对二分查找算法的动态过程的可视化，如代码1-3-2.cpp所示，运行效果参见图1-17，扫描右侧二维码观看视频效果“1.3 二分查找”。
1.3 二分查找
（a）第一次查找，未找到
（b）第二次查找，未找到
（c）第三次查找，未找到
（d）第四次查找，未找到
（e）第五次查找，未找到
（f）第六次查找，找到了
图1-17
1-3-2.cpp
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4 #include <conio.h>
5 #include <windows.h>
6
7 #define LEN 100
8
9 // 自定义函数，输出显示当前查找状态
10 // nums为要查找的数组，statuses记录数组元素的颜色，searchNUM为查找次数，
key为要查找的数值
11 void showArrays(int nums[], int statuses[], int searchNUM, int key)
12 {
13 int i;
14 Sleep(1000); // 暂停
15 system("cls"); // 清空画面
16 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 设为白色
17 printf("在数组中查找：%d\n", key); // 输出白色提示文字
18
19 // 显示当前状态
20 for (i = 0; i < LEN; i++)
21 {
22 // 设为不同的颜色
23 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), statuses[i]);
24 printf("%4d", nums[i]); // 输出对应的数组元素
25 }
26 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 设为白色
27 printf("\n查找次数：%d次\n", searchNUM); // 输出白色提示文字
28 }
29
30 int main() // 主函数
31 {
32 srand((unsigned)time(NULL)); // 初始化随机种子
33 int nums[LEN]; // 要查找的数组
34 int i;
35
36 // 数组元素初始化为1到100
37 for (i = 0; i < LEN; i++)
38 nums[i] = 1 + i;
39
40 // 根据查找状态设定颜色，未查找的数字显示为白色（7），已查找过的数字
显示为灰色（8），正在查找的数字显示为红色（4）
41 int statuses[LEN];
42 for (i = 0; i < LEN; i++)
43 statuses[i] = 7; // 初始全是未查找的数字，显示为白色（7）
44
45 // 生成要查找的数字，为1到100之间的随机整数
46 int key = 1 + rand() % LEN;
47 int id = 0; // 当前查找到的数组元素的索引
48
49 // 定义变量：查找区域的下边界、上边界、正中间
50 int low = 0, high = LEN - 1, mid = (low + high) / 2;
51 int searchNUM = 0; // 查找的次数
52
53 // 以下开始二分查找
54 while (low <= high)
55 {
56 mid = (low + high) / 2; // 正中间元素的序号
57
58 if (key != nums[mid]) // 当前元素不是目标
59 {
60 if (key < nums[mid]) // 下一次查找较小的一半数组
61 high = mid - 1;
62 else // 下一次查找较大的一半数组
63 low = mid + 1;
64 }
65
66 searchNUM++; // 查找次数加1
67 statuses[mid] = 4; // 设置正在查找的元素为红色
68 showArrays(nums, statuses, searchNUM, key); // 显示当前查找状态
69
70 for (i = 0; i < LEN; i++)
71 statuses[i] = 8; // 将数组中所有元素设为灰色
72 for (i = low; i <= high; i++)
73 statuses[i] = 7; // 将下一步要查找范围中的元素设为白色
74
75 if (key != nums[mid]) // 如果没有找到
76 statuses[mid] = 8; // 当前元素设为灰色，表示查找过了
77 else // 如果找到了
78 statuses[mid] = 4; // 当前元素设为红色，表示找到了
79 showArrays(nums, statuses, searchNUM, key); // 显示当前查找状态
80
81 if (key == nums[mid]) // 如果找到了
82 break; // 跳出循环
83 }
84 _getch();
85 return 0;
86 }