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)文章
C++探索構(gòu)造函數(shù)私有化會產(chǎn)生什么結(jié)果
C++的構(gòu)造函數(shù)的作?：初始化類對象的數(shù)據(jù)成員。即類的對象被創(chuàng)建的時候，編譯系統(tǒng)對該對象分配內(nèi)存空間，并?動調(diào)?構(gòu)造函數(shù)，完成類成員的初始化。構(gòu)造函數(shù)的特點：以類名作為函數(shù)名，?返回類型2022-05-05
C語言實現(xiàn)學(xué)籍管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)學(xué)籍管理系統(tǒng)課程設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
C++繼承中的對象構(gòu)造與析構(gòu)和賦值重載詳解
這篇文章主要為大家詳細(xì)介紹了C++繼承中的對象構(gòu)造與析構(gòu)和賦值重載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)電影院選座管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要為大家詳細(xì)介紹了Opencv輕松檢測出圖片中條形碼的10個步驟，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
本文主要介紹了一文詳解C++仿函數(shù),主要用途是提供一種靈活的方式來定義和操作數(shù)據(jù),下面就來介紹一下仿函數(shù)的使用,感興趣的可以了解一下2025-04-04
這篇文章主要介紹了C++的.cpp文件運行全過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
現(xiàn)在正做一個接口，通過不同的連接字符串操作不同的數(shù)據(jù)庫。要用到mysql數(shù)據(jù)庫。通過網(wǎng)上的一些資料和自己的摸索，大致清楚了C++連接mysql的方法?？梢酝ㄟ^2種方法實現(xiàn)。第一種方法是利用ADO連接，第二種方法是利用mysql自己的api函數(shù)進行連接。今天主要來講解下使用API2016-07-07
C++調(diào)用迅雷接口解析XML下載功能(迅雷下載功能)
這篇文章主要介紹了C++調(diào)用迅雷接口，封裝解析XML下載的類，功能簡單，大家參考使用吧2013-11-11
今天小編就為大家分享一篇c語言 字符串的拼接和分割實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12