1.3　二分查找

對(duì)于有序數(shù)組，可以采用更高效的二分查找策略。假設(shè)要在圖1-10所示的數(shù)組中查找數(shù)字6。

圖1-10

首先，將所需查找的數(shù)字6和數(shù)組正中間位置的元素5進(jìn)行比較，如圖1-11所示。

圖1-11

由于6大于5，因此5及其左邊的數(shù)字均不需要再考慮，可以將查找范圍縮減一半，如圖1-12所示。

圖1-12

繼續(xù)將所需查找的數(shù)字6和剩余元素中正中間位置的8進(jìn)行比較，如圖1-13所示。

圖1-13

由于8大于6，因此8及其右邊的數(shù)字均不需要再考慮，如圖1-14所示。

圖1-14

繼續(xù)和剩余元素中正中間位置的6進(jìn)行比較，發(fā)現(xiàn)6即為所查數(shù)字，查找結(jié)束，如圖1-15所示。

圖1-15

假設(shè)有序數(shù)組nums中存儲(chǔ)了n個(gè)數(shù)字，變量key存儲(chǔ)要查找的數(shù)字。二分查找算法比較key和數(shù)組nums正中間位置的元素值，如果key更大，則只需在數(shù)組nums右邊一半的元素中查找；如果key更小，則只需在數(shù)組nums左邊一半的元素中查找。重復(fù)執(zhí)行上述邏輯，即可很快查找到目標(biāo)。二分查找算法的偽代碼如下。

 1    low = 0
 2    high = n - 1
 3    while low <= high
 4        mid = (low + high)/2
 5        if key == nums[mid]
 6            查找成功，跳出循環(huán)
 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() // 主函數(shù)  
 7    {  
 8        srand((unsigned)time(NULL)); // 初始化隨機(jī)種子  
 9        int nums[100]; // 數(shù)組存儲(chǔ)多個(gè)數(shù)字  
10        int i;  
11      
12        // 數(shù)組元素初始化為1到100  
13        for (i = 0; i < 100; i++)  
14            nums[i] = 1 + i;  
15      
16        printf("有序數(shù)組為：");  
17        for (i = 0; i < 100; i++)  
18            printf("%4d", nums[i]);  
19        printf("\n");  
20      
21        // 生成要查找的數(shù)字，為1到100之間的隨機(jī)整數(shù)  
22        int key = 1 + rand() % 100;  
23        int searchNum = 0; // 查找的次數(shù)  
24        // 定義變量：查找區(qū)域的下邊界、上邊界、正中間  
25        int low = 0, high = 100 - 1, mid;  
26      
27        // 以下進(jìn)行二分查找  
28        while (low <= high)  
29        {  
30            searchNum++; // 查找次數(shù)加1  
31            mid = (low + high) / 2; // 正中間元素的序號(hào)  
32            if (key == nums[mid]) // 找到了  
33            {  
34                printf("%d：查找到了，%d是要查找的數(shù)字\n", searchNum, nums[mid]);
35                break; // 跳出while循環(huán)語句  
36            }  
37            else  
38            {  
39                printf("%d：%d不是要查找的數(shù)字\n", searchNum, nums[mid]);  
40                // 更新查找區(qū)域，變成上一步的一半  
41                if (key < nums[mid]) // 下一次查找較小的一半數(shù)組  
42                    high = mid - 1;  
43                else // 下一次查找較大的一半數(shù)組  
44                    low = mid + 1;  
45            }  
46        }  
47        if (low > high) // 沒有找到要查找的數(shù)字  
48            printf("沒有找到要查找的數(shù)字%d\n", key);  
49        _getch();  
50        return 0;  
51    }  

1-3-1.cpp的運(yùn)行效果如圖1-16所示。

圖1-16

將1-2-2.cpp和1-3-1.cpp結(jié)合，即可實(shí)現(xiàn)對(duì)二分查找算法的動(dòng)態(tài)過程的可視化，如代碼1-3-2.cpp所示，運(yùn)行效果參見圖1-17，掃描右側(cè)二維碼觀看視頻效果“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    // 自定義函數(shù)，輸出顯示當(dāng)前查找狀態(tài)  
10    // nums為要查找的數(shù)組，statuses記錄數(shù)組元素的顏色，searchNUM為查找次數(shù)，
    key為要查找的數(shù)值
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); // 設(shè)為白色
17        printf("在數(shù)組中查找：%d\n", key); // 輸出白色提示文字  
18      
19        // 顯示當(dāng)前狀態(tài)  
20        for (i = 0; i < LEN; i++)  
21        {  
22            // 設(shè)為不同的顏色  
23            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), statuses[i]);
24            printf("%4d", nums[i]); // 輸出對(duì)應(yīng)的數(shù)組元素  
25        }  
26        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7); // 設(shè)為白色
27        printf("\n查找次數(shù)：%d次\n", searchNUM); // 輸出白色提示文字  
28    }  
29      
30    int main() // 主函數(shù)  
31    {  
32        srand((unsigned)time(NULL)); // 初始化隨機(jī)種子  
33        int nums[LEN]; // 要查找的數(shù)組  
34        int i;  
35      
36        // 數(shù)組元素初始化為1到100  
37        for (i = 0; i < LEN; i++)  
38            nums[i] = 1 + i;  
39      
40        // 根據(jù)查找狀態(tài)設(shè)定顏色，未查找的數(shù)字顯示為白色（7），已查找過的數(shù)字
    顯示為灰色（8），正在查找的數(shù)字顯示為紅色（4）  
41        int statuses[LEN];   
42        for (i = 0; i < LEN; i++)  
43            statuses[i] = 7; // 初始全是未查找的數(shù)字，顯示為白色（7）  
44      
45        // 生成要查找的數(shù)字，為1到100之間的隨機(jī)整數(shù)  
46        int key = 1 + rand() % LEN;  
47        int id = 0; // 當(dāng)前查找到的數(shù)組元素的索引  
48      
49        // 定義變量：查找區(qū)域的下邊界、上邊界、正中間    
50        int low = 0, high = LEN - 1, mid = (low + high) / 2;  
51        int searchNUM = 0; // 查找的次數(shù)  
52      
53        // 以下開始二分查找  
54        while (low <= high)  
55        {  
56            mid = (low + high) / 2; // 正中間元素的序號(hào)  
57      
58            if (key != nums[mid]) // 當(dāng)前元素不是目標(biāo)  
59            {  
60                if (key < nums[mid]) // 下一次查找較小的一半數(shù)組  
61                    high = mid - 1;  
62                else // 下一次查找較大的一半數(shù)組  
63                    low = mid + 1;  
64            }  
65      
66            searchNUM++; // 查找次數(shù)加1  
67            statuses[mid] = 4; // 設(shè)置正在查找的元素為紅色        
68            showArrays(nums, statuses, searchNUM, key); // 顯示當(dāng)前查找狀態(tài)  
69      
70            for (i = 0; i < LEN; i++)  
71                statuses[i] = 8; // 將數(shù)組中所有元素設(shè)為灰色  
72            for (i = low; i <= high; i++)  
73                statuses[i] = 7; // 將下一步要查找范圍中的元素設(shè)為白色  
74      
75            if (key != nums[mid]) // 如果沒有找到   
76                statuses[mid] = 8; // 當(dāng)前元素設(shè)為灰色，表示查找過了  
77            else // 如果找到了  
78                statuses[mid] = 4; // 當(dāng)前元素設(shè)為紅色，表示找到了  
79            showArrays(nums, statuses, searchNUM, key); // 顯示當(dāng)前查找狀態(tài)  
80      
81            if (key == nums[mid]) //  如果找到了
82                break;  //  跳出循環(huán)
83        }  
84        _getch();  
85        return 0;  
86    }