我們常常需要對數據進行查找，修改，查找數據有許多方法，我們先看看最簡單的順序查找
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int main(){ int i, k = 0; scanf("%d", &k); int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < sz; i++) { if (arr[i] == k) { printf("找到了，它是%d", arr[i]); } } return 0;} |
順序查找絕大多數情況有效但是由于它是一個一個元素進行查找，其效率很低，只有一個for循環所有其時間復雜度為O（n）。我們希望有一個更高效的查找方法，接下來便是二分查找，先來看看一個順序查找和二分查找的直觀比較。
從上面的圖中我們感受到二分查找的關鍵：找到最左邊元素（low）和最右邊元素（high），確定中間元素（mid），比較中間元素（mid）和目標元素（k）的大小，調整low和high，再確定新的mid....我們要不斷確定mid直到找到k，自然需要用到循環，我們有明確的目標：找到k。因此選擇while循環，找到k后循環不再進行，而當low和high之間還有元素，即low在high的左邊或與之重合，k就依然可能存在，所以循環條件為low<=high，接下來的問題在于怎樣調整low和high的值，mid和k比較無非就三種情況：mid<k，mid>k,mid=k。第一種情況，k在mid的右邊，我們將low調整為mid+1，high不用調整；第二種情況，k在mid的左邊，我們將high調整為mid-1，low不用調整。最后一種情況最簡單，我們已經找到了k，直接將mid打印出來就行了，代碼如下：
|
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
|
#include <stdio.h>int main(){ int k = 0; scanf("%d", &k); int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz = sizeof(arr) / sizeof (arr[0]); int low = 0; int high = sz-1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] > k) { high = mid - 1; } else if (arr[mid] < k) { low = mid + 1; } else { printf("找到了，它是：%d", arr[a]); break; } } if (l>r) printf("沒找到，請重新輸入"); return 0;} |
二分查找的時間復雜度的問題：總共有n個元素，每次查找的區間大小就是n，n/2，n/4，…，n/2^k（接下來操作元素的剩余個數），其中k就是循環的次數。由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2為底，n的對數），所以時間復雜度可以表示O(logn)，確實比順序查找快不少，但是二分查找有一個較大的局限性:只能查找有序數組的元素，即組數字必須是升序或降序。
總結
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關注服務器之家的更多內容！
原文鏈接：https://blog.csdn.net/ZDDWLIG/article/details/119886256
