1.2　顺序查找

猜数字游戏的策略可以转换为不同的查找算法。首先，我们学习最简单的顺序查找算法。假设要在图1-3所示的数组中查找数字7。

顺序查找算法首先检查数组中的第一个元素5，将之与待查找数字7进行比较，如图1-4所示。如果相等，则查找结束；如果不等，则继续向右查找。

5不等于7，继续比对第二个元素，如图1-5所示。

1不等于7，继续向右查找，直到找到数字7，查找结束，如图1-6所示。

假设数组nums中存储了 n 个数字，变量key中存储要查找的数字。顺序查找算法从数组nums中的第一个元素开始，依次与变量key进行比较；直至找到相等的元素，循环停止。顺序查找算法的伪代码如下。

1    for i从0到n-1
 2        if nums[i]==key
 3            查找成功，结束for循环
 4    if i==n
 5        查找失败

顺序查找算法的完整代码如1-2-1.cpp所示。

1-2-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        // 随机交换数组中元素的顺序
17        for (i = 0; i < 50; i++)  
18        {  
19            int ri = rand() % 100; // 第1个数字的索引
20            int rj = rand() % 100; // 第2个数字的索引
21            // 交换数组中这两个数字的顺序  
22            int temp = nums[ri];  
23            nums[ri] = nums[rj];  
24            nums[rj] = temp;  
25        }  
26      
27        printf("随机数组为：");  
28        for (i = 0; i < 100; i++)  
29            printf("%4d", nums[i]);  
30        printf("\n");  
31      
32        // 生成要查找的数字，为1到100之间的随机整数  
33        int key = 1 + rand() % 100;  
34      
35        // 以下开始顺序查找  
36        for (i = 0; i < 100; i++)  
37        {  
38            if (key != nums[i])  
39            {  
40                printf("%d：%d不是要查找的数字\n", i, nums[i]);  
41            }  
42            else  
43            {  
44                printf("%d：查找到了，%d是要查找的数字\n", i, nums[i]);  
45                break; // 终止for循环  
46            }  
47        }  
48        if (i == 100)  
49            printf("没有找到数字%d\n", key);  
50        _getch();  
51        return 0;  
52    } 

1-2-1.cpp的运行效果如图1-7所示。

为了展示顺序查找算法的动态过程，可以利用Sleep()函数暂停若干毫秒，利用system("cls")清空画面，利用SetConsoleTextAttribute()设置字符显示不同的颜色，如代码1-2-2.cpp所示。

1-2-2.cpp

1    #include <stdio.h>  
 2    #include <windows.h>  
 3    #include <conio.h>  
 4    int main()  
 5    {  
 6        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 8);  
 7        printf("已查找过的显示为灰色\n");  
 8      
 9        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4);  
10        printf("正在查找的显示为红色\n");  
11      
12        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);  
13        printf("未查找的显示为白色\n");  
14          
15        Sleep(5000); // 暂停  
16        system("cls"); // 清空画面  
17      
18        _getch();  
19        return 0;  
20    }

运行代码1-2-2.cpp后，首先输出不同颜色的字符，如图1-8所示，5秒后清除所显示的内容。

将1-2-2.cpp和1-2-1.cpp结合，即可实现对顺序查找算法的动态过程的可视化，如代码1-2-3.cpp所示，运行效果参见图1-9，扫描下方二维码观看视频效果“1.2 顺序查找”。

1-2-3.cpp kxa6mKHCrm8Sh2y8G+Dz5W9/f93qZFGY0tm436C0SPC53E4TGY4/XtDBGDXn41wd

 1    #include <stdio.h>  
 2    #include <stdlib.h>  
 3    #include <conio.h>  
 4    #include <time.h>  
 5    #include <windows.h>  
 6      
 7    #define LEN 100  
 8      
 9    int main() // 主函数  
10    {  
11        srand((unsigned)time(NULL)); // 初始化随机种子  
12        int nums[LEN]; // 数组存储多个数字  
13        int i;  
14      
15        // 数组元素初始化为1到100  
16        for (i = 0; i < LEN; i++)  
17            nums[i] = 1 + i;  
18      
19        // 随机交换数组中元素的顺序
20        for (i = 0; i < 50; i++)  
21        {  
22            int ri = rand() % 100; // 第1个数字的索引
23            int rj = rand() % 100; // 第2个数字的索引
24            // 交换数组中这两个数字的顺序  
25            int temp = nums[ri];  
26            nums[ri] = nums[rj];  
27            nums[rj] = temp;  
28        }  
29      
30        // 生成要查找的数字，为1到100之间的随机整数  
31        int key = 1 + rand() % LEN;  
32        int id = 0; // 当前查找到的数组元素的索引  
33      
34        // 以下开始顺序查找  
35        for (id = 0; id < LEN; id++)  
36        {  
37            Sleep(100); // 暂停100毫秒  
38            system("cls"); // 清空画面  
39            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 白色
40            printf("在数组中查找：%d\n", key);  
41      
42            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 8); // 灰色
43            // 已经查找过的元素显示为灰色  
44            for (i = 0; i < id; i++)  
45                printf("%4d", nums[i]);  
46      
47            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 4); // 红色
48            // 正在被查找的元素显示为红色  
49            printf("%4d", nums[id]);  
50      
51            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 白色
52            // 还没有被查找的元素显示为白色  
53            for (i = id + 1; i < LEN; i++)  
54                printf("%4d", nums[i]);  
55            printf("\n查找次数：%d次\n", id);  
56      
57            if (key == nums[id])  
58                break; // 查找到了，跳出for循环语句  
59        }  
60        _getch();  
61        return 0;  
62    }