C語言實現折半查找法（二分法）
更新時間：2020年11月01日 12:27:01 作者：_MaL
這篇文章主要為大家詳細介紹了C語言實現折半查找法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
折半查找法也叫做二分查找，顧名思義，就是把數據分成兩半，再判斷所查找的key在哪一半中，再重復上述步驟知道找到目標key;
注意：折半查找法僅適用于對已有順序的數組、數據進行操作?。。?/span>
很顯然，折半查找法相對于其他查找方法例如順序查找法效率要高很多；
下面我們來實際操作一下，了解二分查找的奧義。
例如：要在數組arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置；首先，我們要先將數組arr中的數據成員進行排序。arr[]={1,2,3,4,5,6,7,8,9,10,11};
如圖所示：將該組數據小端記作low，大端記作high,中間值記作mid;
二分法查找時，將所查找的key與mid比較，例如key=7，即可縮小查找范圍在mid和high之間；
如圖所示即可找到key=low=7;
注意： （敲黑板）如果中間數mid不是整數，需要進行取整。
代碼如下：
#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; //如果數組中無目標值key，則返回 -1 ；
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11}; //首先要對數組arr進行排序
printf("%d \n",BinSearch(arr,(sizeof(arr)/sizeof(arr[0])),7));
return 0;
}
運行結果如下：
希望對您有所幫助！
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
本篇文章是對c語言中printf函數的使用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
對于字符,在計算機內部都是用數字（字符編碼）來表示的,而字符串是“字符連續(xù)排列”的一種表現,這篇文章主要給大家介紹了關于C語言進階教程之字符串&內存函數的相關資料,需要的朋友可以參考下2021-09-09
這里給大家介紹了C++中對于pthread線程的一個簡單應用以及使用繼承CDoit，實現其中的start和end，有需要的小伙伴可以參考下2015-11-11
這篇文章主要介紹了詳解C++函數模板與分離編譯模式的相關資料，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2020-08-08
這篇文章主要為大家詳細介紹了C++實現歸并排序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要介紹了C++對string進行大小寫轉換操作方法,本文通過兩種方法結合實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2023-02-02
鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的，本章帶你詳細了解鏈表與單鏈表2022-02-02
在本篇文章里小編給大家整理的是一篇關于C++中隱式類型轉換學習筆記內容，有興趣的跟著小編來學習下吧。2020-02-02
函數棧幀（stack frame）就是函數調用過程中在程序的調用棧（call stack）所開辟的空間,下面這篇文章主要給大家介紹了關于C語言函數棧幀的創(chuàng)建與銷毀的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-09-09
這篇文章主要為大家詳細介紹了Qt如何利用QState狀態(tài)機實現控件互斥操作，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2022-12-12