題目
首先我們來把題目瞅一眼：
在一個有序數組中查找具體的某個數字n。
編寫int binary_search (int x, int v[], int n);
功能：在v [0] <= v [1] <= v [2] <= …. <= v [n-1]的數組中查找x.
題目大概的意思就是說這是一串有序的數組，我們編寫代碼完成以下功能：如果輸入的數字在數組中，就輸出找到了并輸出下標，如果輸入的數字不在數組中則輸出找不到。
下面看解法：
解法一： 挨個遍歷
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <stdio.h>int main(){ int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; //查找7 //遍歷 0 ~ sz - 1 int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; int flag = 0;//0表示沒有找到 for (i = 0; i < sz; i++) { if(7 == arr[i]) { flag = 1; break; } } if (1 == flag) printf("找到了，下標是：%d\n", i); else printf("沒找到\n"); return 0;} |
博主這里的代碼為了讓大家可以看的更清楚，所以沒有寫成輸入的模式，而是直接想要查找7。
這是萬能的方法，就挨個遍歷，有就是有，沒有就是沒有，屬實牛批，但缺點是太費時間，如果要查找1 - 10000000中的10000000，那未免也太久了，既然這樣的數組是一串有序的數組，不妨我們可以試試二分查找/折半查找。
方法二：折半查找/二分查找（僅適用于有序查找）
方法分析：
下面分析一下折半查找是怎么實現的，比如我們的數組是1 - 10，想要查找的數是7，那我們知道下標為0的數組對于1，下標為9的數組對于10，那我們則應該先找到中間下標對應的元素arr[mid]，讓他和7比較，如果比7大，則將最右邊的下標賦值為mid - 1，反之，則將最左邊下標賦值為mid + 1，這樣循環往復無限逼近要查找的數，每次排查一半，直到arr[mid] == 7，就找到了，如果直到最左下標和最右下標重合之后都找不到，那這個數一定不在這個有序數組內。
下面我們看代碼是怎么寫的：
代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <stdio.h>int main(){ int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; //查找7 //0 ~ sz - 1 int sz = sizeof (arr) / sizeof (arr[0]); int left = 0; int right = sz - 1; int mid = 0; int k = 7;//要查找的元素 int flag = 0; while(left <= right) // 即使是 left == right,也有一個元素需要被查找 { //求中間元素下標 mid = (left + right) / 2; // 每一次二分查找都要求出新的中間元素下標 if(arr[mid] < k) { left = mid + 1; } else if (arr[mid] > k) { right = mid - 1; } else { //找到了 flag = 1; break; } } if (1 == flag) printf("找到了，下標是：%d\n", mid); else printf("找不到\n"); return 0;} |
雖然折半查找看起來代碼比遍歷查找多一些，但其實中間省了非常多計算機計算的時間，非常好用~~
總結
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關注服務器之家的更多內容！
原文鏈接：https://blog.csdn.net/Aaron_skr/article/details/119873642
