C經(jīng)典算法之二分查找法
更新時(shí)間：2017年10月05日 10:00:40 作者：CharlinGod
這篇文章主要介紹了C經(jīng)典算法之二分查找法的相關(guān)資料,這里提供兩種方法幫助大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下
C經(jīng)典算法之二分查找法
1.根據(jù)key查找所在數(shù)組的位置
#include <stdio.h>
/*
key = 9;
1 2 3 4 5 6 7 8
arr 3， 4， 5， 7， 9 ， 11， 21， 23
low = 1 mid = (low + high)/2 = 4 high = 8;
one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
two arr[mid] = 11 > 9 so low = 5 , high = mid - 1 = 5 mid = 5;
arr[mid] = 9 == key
if(key = 10) low = mid + 1 > high
*/
int main(int argc, const char * argv[])
{
int findByHalf(int arr[], int len, int key);
int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
int len = sizeof(arr)/sizeof(int);
int index = findByHalf(arr, len, 88);
printf("index = %d\n", index);
return 0;
}
int findByHalf(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]) {
low = mid + 1;
//左邊查找
}else if (key > arr[mid]) {
high = mid - 1;
}else{
return mid;
}
}
return -1;
}
2.插入一個(gè)數(shù)，得到其所在數(shù)組的位置
#include <stdio.h>
/*
key = 9;
1 2 3 4 5 6 7 8
arr 3， 4， 5， 7， 9 ， 11， 21， 23
low = 1 mid = (low + high)/2 = 4 high = 8;
one arr[mid] = 7 < 9; so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
two arr[mid] = 11 > 9 so low = 5 , high = mid - 1 = 5 mid = 5;
arr[mid] = 9 == key
if(key = 10) low = mid + 1 > high
*/
int main(int argc, const char * argv[])
{
int findByHalf(int arr[], int len, int key);
int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
int len = sizeof(arr)/sizeof(int);
int index = findByHalf(arr, len, 88);
printf("index = %d\n", index);
return 0;
}
int insertByHalf(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]) {
low = mid + 1;
//左邊查找
}else if (key > arr[mid]) {
high = mid - 1;
}else{
//如果arr[mid] == key
//就把key插入到這個(gè)數(shù)的后面
return mid + 1;
}
}
//如果low > high 說(shuō)明 key > arr[mid];
//就把key插入到low對(duì)應(yīng)的 這個(gè)數(shù)的位置
return low;
}
如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
這篇文章主要介紹了MFC實(shí)現(xiàn)全屏功能的代碼,對(duì)于學(xué)習(xí)MFC有一定的借鑒價(jià)值,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)通訊錄功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
老生常談C語(yǔ)言靜態(tài)函數(shù)庫(kù)的制作和使用
下面小編就為大家?guī)?lái)一篇老生常談C語(yǔ)言靜態(tài)函數(shù)庫(kù)的制作和使用。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-08-08
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)雙向冒泡排序算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要介紹了C++繼承和動(dòng)態(tài)內(nèi)存分配，當(dāng)我們的基類使用動(dòng)態(tài)內(nèi)存分配，并且重新定義賦值和復(fù)制構(gòu)造函數(shù)，這會(huì)對(duì)派生類的實(shí)現(xiàn)有什么影響呢？我們帶罩疑問(wèn)倆姐下面文章內(nèi)容吧2022-01-01
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之線索二叉樹(shù)及其遍歷
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之線索二叉樹(shù)及其遍歷的相關(guān)資料,為了加快查找節(jié)點(diǎn)的前驅(qū)和后繼。對(duì)二叉樹(shù)的線索化就是對(duì)二叉樹(shù)進(jìn)行一次遍歷，在遍歷的過(guò)程中檢測(cè)節(jié)點(diǎn)的左右指針是否為空，如果是空，則將他們改為指向前驅(qū)和后繼節(jié)點(diǎn)的線索，需要的朋友可以參考下2017-08-08
C語(yǔ)言進(jìn)階輸入輸出重定向與fopen函數(shù)使用示例詳解
這篇文章主要為大家介紹了C語(yǔ)言進(jìn)階輸入輸出重定向與fopen函數(shù)的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
這篇文章主要介紹了C++讀寫(xiě)INI配置文件的類,實(shí)例分析了C++操作ini配置文件的相關(guān)技巧,需要的朋友可以參考下2015-06-06
構(gòu)造函數(shù)主要作用在于創(chuàng)建對(duì)象時(shí)為對(duì)象的成員屬性賦值，構(gòu)造函數(shù)由編譯器自動(dòng)調(diào)用,無(wú)須手動(dòng)調(diào)用，這篇文章詳細(xì)介紹了構(gòu)造函數(shù)的初始化列表，文章中有詳細(xì)的示例代碼，感興趣的同學(xué)可以參考閱讀2023-04-04
C/C++?Qt?運(yùn)用JSON解析庫(kù)的實(shí)例代碼
這篇文章主要介紹了C/C++?Qt?運(yùn)用JSON解析庫(kù)的相關(guān)知識(shí)，通過(guò)代碼依次解析這個(gè)json文件中的每一個(gè)參數(shù)，代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-01-01