一篇文章帶你了解C語(yǔ)言二分查找
我們常常需要對(duì)數(shù)據(jù)進(jìn)行查找，修改，查找數(shù)據(jù)有許多方法，我們先看看最簡(jiǎn)單的順序查找
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ù)情況有效但是由于它是一個(gè)一個(gè)元素進(jìn)行查找，其效率很低，只有一個(gè)for循環(huán)所有其時(shí)間復(fù)雜度為O（n）。我們希望有一個(gè)更高效的查找方法，接下來(lái)便是二分查找，先來(lái)看看一個(gè)順序查找和二分查找的直觀比較。
從上面的圖中我們感受到二分查找的關(guān)鍵：找到最左邊元素（low）和最右邊元素（high），確定中間元素（mid），比較中間元素（mid）和目標(biāo)元素（k）的大小，調(diào)整low和high，再確定新的mid....我們要不斷確定mid直到找到k，自然需要用到循環(huán)，我們有明確的目標(biāo)：找到k。因此選擇while循環(huán)，找到k后循環(huán)不再進(jìn)行，而當(dāng)low和high之間還有元素，即low在high的左邊或與之重合，k就依然可能存在，所以循環(huán)條件為low<=high，接下來(lái)的問(wèn)題在于怎樣調(diào)整low和high的值，mid和k比較無(wú)非就三種情況：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)整。最后一種情況最簡(jiǎn)單，我們已經(jīng)找到了k，直接將mid打印出來(lái)就行了，代碼如下：
#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("沒(méi)找到，請(qǐng)重新輸入");
return 0;
}
二分查找的時(shí)間復(fù)雜度的問(wèn)題：總共有n個(gè)元素，每次查找的區(qū)間大小就是n，n/2，n/4，…，n/2^k（接下來(lái)操作元素的剩余個(gè)數(shù)），其中k就是循環(huán)的次數(shù)。由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2為底，n的對(duì)數(shù)），所以時(shí)間復(fù)雜度可以表示O(logn)，確實(shí)比順序查找快不少，但是二分查找有一個(gè)較大的局限性:只能查找有序數(shù)組的元素，即組數(shù)字必須是升序或降序。
總結(jié)
本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
C++ OpenCV繪制簡(jiǎn)易直方圖DrawHistImg
本文主要介紹了一個(gè)能繪制簡(jiǎn)易直方圖的簡(jiǎn)單函數(shù)DrawHistImg，可以幫助大家快速掌握繪制的原理，可以根據(jù)自己的創(chuàng)意對(duì)其進(jìn)行改善和補(bǔ)充。需要的朋友可以參考一下2021-12-12
C語(yǔ)言?超詳細(xì)總結(jié)講解二叉樹(shù)的概念與使用
二叉樹(shù)可以簡(jiǎn)單理解為對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，最多擁有一個(gè)上級(jí)節(jié)點(diǎn)，同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。本文將詳細(xì)介紹一下C++中二叉樹(shù)的概念和結(jié)構(gòu)，需要的可以參考一下2022-04-04
非常漂亮的新年祝福!C語(yǔ)言實(shí)現(xiàn)漂亮的煙花效果
非常漂亮的新年祝福！這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)漂亮的煙花效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
Windows下ncnn環(huán)境配置教程詳解（VS2019）
這篇文章主要介紹了Windows下ncnn環(huán)境配置（VS2019）,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-03-03
這篇文章主要介紹了C語(yǔ)言中的多級(jí)指針,本文給大家介紹的非常詳細(xì)，具有參考借鑒價(jià)值，需要的朋友可以參考下,希望能給你帶來(lái)幫助2021-08-08
C++可調(diào)用對(duì)象callable object深入分析
所謂的callable object，表示可以被某種方式調(diào)用其某些函數(shù)的對(duì)象。它可以是：一個(gè)函數(shù)、一個(gè)指向成員函數(shù)的指針、一個(gè)函數(shù)對(duì)象，該對(duì)象擁有operator()、一個(gè)lambda表達(dá)式，嚴(yán)格的說(shuō)它是一種函數(shù)對(duì)象2022-08-08
這篇文章主要介紹了windows下vscode使用cmake的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
C++?測(cè)試框架GoogleTest入門(mén)介紹
這篇文章主要為大家介紹了C++測(cè)試框架GoogleTest入門(mén)基礎(chǔ)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
這篇文章主要介紹了C++中的內(nèi)存對(duì)齊實(shí)例詳解的相關(guān)資料,這里不僅提供實(shí)現(xiàn)方法及代碼還提供了手工制作圖，來(lái)幫助到大家理解這部分知識(shí)，需要的朋友可以參考下2017-07-07
C++依賴(lài)倒轉(zhuǎn)原則和里氏代換原則有什么好處
設(shè)計(jì)模式（Design pattern）代表了最佳的實(shí)踐，通常被有經(jīng)驗(yàn)的面向?qū)ο蟮能浖_(kāi)發(fā)人員所采用。設(shè)計(jì)模式是軟件開(kāi)發(fā)人員在軟件開(kāi)發(fā)過(guò)程中面臨的一般問(wèn)題的解決方案。本篇介紹設(shè)計(jì)模式七大原則之一的依賴(lài)倒轉(zhuǎn)原則2023-02-02