一篇文章帶你了解C語言二分查找
我們常常需要對數(shù)據(jù)進行查找,修改,查找數(shù)據(jù)有許多方法,我們先看看最簡單的順序查找
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; }
順序查找絕大多數(shù)情況有效但是由于它是一個一個元素進行查找,其效率很低,只有一個for循環(huán)所有其時間復(fù)雜度為O(n)。我們希望有一個更高效的查找方法,接下來便是二分查找,先來看看一個順序查找和二分查找的直觀比較。
從上面的圖中我們感受到二分查找的關(guān)鍵:找到最左邊元素(low)和最右邊元素(high),確定中間元素(mid),比較中間元素(mid)和目標元素(k)的大小,調(diào)整low和high,再確定新的mid....我們要不斷確定mid直到找到k,自然需要用到循環(huán),我們有明確的目標:找到k。因此選擇while循環(huán),找到k后循環(huán)不再進行,而當low和high之間還有元素,即low在high的左邊或與之重合,k就依然可能存在,所以循環(huán)條件為low<=high,接下來的問題在于怎樣調(diào)整low和high的值,mid和k比較無非就三種情況:mid<k,mid>k,mid=k。第一種情況,k在mid的右邊,我們將low調(diào)整為mid+1,high不用調(diào)整;第二種情況,k在mid的左邊,我們將high調(diào)整為mid-1,low不用調(diào)整。最后一種情況最簡單,我們已經(jīng)找到了k,直接將mid打印出來就行了,代碼如下:
#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; }
二分查找的時間復(fù)雜度的問題:總共有n個元素,每次查找的區(qū)間大小就是n,n/2,n/4,…,n/2^k(接下來操作元素的剩余個數(shù)),其中k就是循環(huán)的次數(shù)。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2為底,n的對數(shù)),所以時間復(fù)雜度可以表示O(logn),確實比順序查找快不少,但是二分查找有一個較大的局限性:只能查找有序數(shù)組的元素,即組數(shù)字必須是升序或降序。
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
Windows下ncnn環(huán)境配置教程詳解(VS2019)
這篇文章主要介紹了Windows下ncnn環(huán)境配置(VS2019),本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03C++可調(diào)用對象callable object深入分析
所謂的callable object,表示可以被某種方式調(diào)用其某些函數(shù)的對象。它可以是:一個函數(shù)、一個指向成員函數(shù)的指針、一個函數(shù)對象,該對象擁有operator()、一個lambda表達式,嚴格的說它是一種函數(shù)對象2022-08-08