C語言實(shí)現(xiàn)折半查找法（二分法）
更新時(shí)間：2020年11月01日 12:27:01 作者：_MaL
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)折半查找法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
折半查找法也叫做二分查找，顧名思義，就是把數(shù)據(jù)分成兩半，再判斷所查找的key在哪一半中，再重復(fù)上述步驟知道找到目標(biāo)key;
注意：折半查找法僅適用于對(duì)已有順序的數(shù)組、數(shù)據(jù)進(jìn)行操作！??！
很顯然，折半查找法相對(duì)于其他查找方法例如順序查找法效率要高很多；
下面我們來實(shí)際操作一下，了解二分查找的奧義。
例如：要在數(shù)組arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置；首先，我們要先將數(shù)組arr中的數(shù)據(jù)成員進(jìn)行排序。arr[]={1,2,3,4,5,6,7,8,9,10,11};
如圖所示：將該組數(shù)據(jù)小端記作low，大端記作high,中間值記作mid;
二分法查找時(shí)，將所查找的key與mid比較，例如key=7，即可縮小查找范圍在mid和high之間；
如圖所示即可找到key=low=7;
注意： （敲黑板）如果中間數(shù)mid不是整數(shù)，需要進(jìn)行取整。
代碼如下：
#include<stdio.h>
int BinSearch(int arr[],int len,int key) //折半查找法（二分法）
{
int low=0; //定義初始最小
int high=len-1; //定義初始最大
int mid; //定義中間值
while(low<=high)
{
mid=(low+high)/2; //找中間值
if(key==arr[mid]) //判斷min與key是否2020111122411718相等
return mid;
else if(key>arr[mid]) //如果key>mid 則新區(qū)間為[mid+1,high]
low=mid+1;
else //如果key<mid 則新區(qū)間為[low,mid-1]
high=mid-1;
}
return -1; //如果數(shù)組中無目標(biāo)值key，則返回 -1 ；
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11}; //首先要對(duì)數(shù)組arr進(jìn)行排序
printf("%d \n",BinSearch(arr,(sizeof(arr)/sizeof(arr[0])),7));
return 0;
}
運(yùn)行結(jié)果如下：
希望對(duì)您有所幫助！
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C++內(nèi)存分區(qū)包括棧區(qū)、堆區(qū)、全局靜態(tài)區(qū)、常量區(qū)，各自負(fù)責(zé)不同的數(shù)據(jù)存儲(chǔ)和回收，棧區(qū)主要用于存放函數(shù)局部變量和參數(shù)，堆區(qū)用于動(dòng)態(tài)分配內(nèi)存，全局靜態(tài)區(qū)用于存放全局靜態(tài)變量和靜態(tài)成員變量，常量區(qū)用于存放常量和字符串常量2023-04-04
工程上寫代碼應(yīng)分為多個(gè)文件,那么你知道C語言工程文件該如何寫嗎,本文就以以三子棋游戲?yàn)槔?介紹一下,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
求余運(yùn)算符“%”，二元運(yùn)算符，具有左結(jié)合性。參與運(yùn)算的量均為整型。求余運(yùn)算的結(jié)果等于兩個(gè)數(shù)相除后的余數(shù)。看似很簡單的運(yùn)算符，卻也真要掌握用好它也不容易，這篇文章主要介紹了C++中求余運(yùn)算符(%)的相關(guān)資料,需要的朋友可以參考借鑒，下面來一起看看吧。2017-01-01
這篇文章主要為大家分享了C語言UDP傳輸系統(tǒng)的源碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
詳解MFC/C++調(diào)用易語言的整數(shù)型和文本型與VS2010互動(dòng)
在本篇文章里我們給大家分享了MFC/C++調(diào)用易語言的整數(shù)型和文本型與VS2010互動(dòng)相關(guān)知識(shí)點(diǎn)內(nèi)容，有興趣的朋友們可以參考下。2018-11-11
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單推箱子游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了C++利用鏈表寫一個(gè)簡單的棧實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05
相較單鏈表，雙向鏈表除了data與next域，還多了一個(gè)pre域用于表示每個(gè)節(jié)點(diǎn)的前一個(gè)元素。這樣做給雙向鏈表帶來了很多優(yōu)勢(shì)。本文主要介紹了雙向鏈表的實(shí)現(xiàn)，需要的可以參考一下2023-03-03
一文詳解C語言中的switch語句和while循環(huán)
這篇文章主要給大家詳細(xì)介紹了C語言中的switch語句和while循環(huán)，文中通過代碼示例給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2023-12-12
C語言數(shù)據(jù)結(jié)構(gòu)創(chuàng)建及遍歷十字鏈表
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)十字鏈表的創(chuàng)建及遍歷，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2021-10-10