C語言數(shù)據結構之二分法查找詳解
更新時間：2022年02月10日 15:49:52 作者：誠摯的喬治
二分查找算法是在有序數(shù)組中用到的較為頻繁的一種算法，在未接觸二分查找算法時，最通用的一種做法是，對數(shù)組進行遍歷，跟每個元素進行比較，其時間為O(n)，但二分查找算法更優(yōu)
問題：在有序數(shù)組中查找給定元素的下標goal。
在查找一個數(shù)組元素的下標，可以用循環(huán)來解決，但是如果一個數(shù)足夠大，比如說手機的價格，用循環(huán)來查找，就相當于叫一個人猜，從0開始，需要猜很久。這時候就出現(xiàn)了二分查找，也叫對半查找。
對半查找顧名思義就是猜一次，下次猜的內容就減少一半? ? ? ? ? ? ?
這時候定義一個變量left表示最左邊元素的下標，在定義一個right表示最右邊元素的下標，而mid就表示中間元素的下標。
當中間值小于目標值，left重新定義。
if (mid < goal)
{
left = mid + 1;
}
當中間值大于目標元素，right重新定義。
else if (mid > goal)
{
right = mid - 1;
}
當中間元素等于目標元素時，打印即可。
else
{
printf("你找到了，下標為：%d", mid);
break;
}
這中查找方式可能會使用多次，這時候來一個while循環(huán)就可以重復查找的撒
如果最后數(shù)組元素找不到對應的元素，就在while循環(huán)外打印出找不到。
if (left > right)
printf("找不到");
最后代碼如下：
#include<stdio.h>//在數(shù)組中找到某個數(shù),二分查找
int main()
{
int goal = 7;
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof arr[0];
int left = 0; int right = sz - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (mid < goal)
{
left = mid + 1;
}
else if (mid > goal)
{
right = mid - 1;
}
else
{
printf("找到了，下標為：%d", mid);
break;
}
}
if (left > right)
printf("找不到");
return 0;
}
到此這篇關于C語言數(shù)據結構之二分法查找詳解的文章就介紹到這了,更多相關C語言 二分法查找內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了CMakeList中自動編譯protobuf文件過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
QScrollArea是Qt框架中用于提供一個滾動條區(qū)域,允許用戶滾動查看比當前可視區(qū)域更大的內容的控件,本文主要介紹了Qt中QScrollArea控件的實現(xiàn),感興趣的可以了解一下2025-04-04
Qt提供了QDomElement 類用于完成對xml文件的讀取和寫入,這篇文章主要給大家介紹了關于C++、Qt分別讀寫xml文件的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-03-03
這篇文章主要介紹了opencv攝像頭捕獲識別顏色，用opencv通過攝像頭捕獲識別顏色，紅色藍色等，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07
今天發(fā)現(xiàn)網上好多MFC代碼都不能用，給大家分享一個簡單的MFC窗口語言，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了C語言跳轉瀏覽器打開指定URL,該代碼使用sprintf()函數(shù)將要打開的URL添加到一個系統(tǒng)命令中，然后使用system()函數(shù)調用該命令以默認瀏覽器打開URL,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了VC定制個性化的MessageBox解決方法,有助于進一步的了解windows應用程序的消息機制及運行原理,需要的朋友可以參考下2014-07-07
本文主要介紹了C++通過文件指針獲取文件大小的方法實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
Qt是一種C++編程框架,用于構建圖形用戶界面（GUI）應用程序和嵌入式系統(tǒng),無論是初學者還是經驗豐富的開發(fā)者,Qt都為構建高質量、可維護的應用程序提供了豐富的工具和支持,本文主要給大家介紹了C++中Qt的安裝與配置步驟,需要的朋友可以參考下2023-12-12
本篇文章是對《C和指針》這本書的學習做了筆記介紹。需要的朋友參考下2013-05-05