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