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