- 相關(guān)推薦
C語(yǔ)言二分查找（折半查找）算法及代碼
C語(yǔ)言是一種結(jié)構(gòu)化語(yǔ)言,它有著清晰的層次,可按照模塊的方式對(duì)程序進(jìn)行編寫,十分有利于程序的調(diào)試,且c語(yǔ)言的處理和表現(xiàn)能力都非常的強(qiáng)大,依靠非常全面的運(yùn)算符和多樣的數(shù)據(jù)類型,可以輕易完成各種數(shù)據(jù)結(jié)構(gòu)的構(gòu)建,以下是小編幫大家整理的C語(yǔ)言二分查找（折半查找）算法及代碼，歡迎大家借鑒與參考，希望對(duì)大家有所幫助。
二分査找也稱折半査找，其優(yōu)點(diǎn)是查找速度快，缺點(diǎn)是要求所要査找的數(shù)據(jù)必須是有序序列。該算法的基本思想是將所要査找的序列的中間位置的數(shù)據(jù)與所要査找的元素進(jìn)行比較，如果相等，則表示査找成功，否則將以該位置為基準(zhǔn)將所要査找的序列分為左右兩部分。接下來(lái)根據(jù)所要査找序列的升降序規(guī)律及中間元素與所查找元素的大小關(guān)系，來(lái)選擇所要査找元素可能存在的那部分序列，對(duì)其采用同樣的方法進(jìn)行査找，直至能夠確定所要查找的元素是否存在，具體的使用方法可通過(guò)下面的代碼具體了解。
#include
binarySearch(int a[], int n, int key){
int low = 0;
int high = n - 1;
while(low<= high){
int mid = (low + high)/2;
int midVal = a[mid];
if(midVal<key)< p="">
low = mid + 1;
else if(midVal>key)
high = mid - 1;
else
return mid;
}
return -1;
}
int main(){
int i, val, ret;
int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf(" 請(qǐng)輸人所要查找的元素：");
scanf("%d",&val);
ret = binarySearch(a,8,val);
if(-1 == ret)
printf("查找失敗 ");
else
printf ("查找成功 ");
return 0;
}
運(yùn)行結(jié)果：
-32 12 16 24 36 45 59 98
請(qǐng)輸入所要查找的元素：12
查找成功
在上面的代碼中，我們成功地通過(guò)二分査找算法實(shí)現(xiàn)了查找功能，其實(shí)現(xiàn)過(guò)程如下 所示。
在如上圖所示的查找過(guò)程中，先將序列中間位置的元素與所要査找的元素進(jìn)行比較，發(fā)現(xiàn)要査找的元素位干該位置的左部分序列中。接下來(lái)將mid的左邊一個(gè)元素作為 high，繼續(xù)進(jìn)行二分査找，這時(shí)mid所對(duì)應(yīng)的中間元素剛好是所要査找的元素，査找結(jié)束，返回査找元素所對(duì)應(yīng)的下標(biāo)。在main函數(shù)中通過(guò)返回值來(lái)判斷査找是否成功，如果査找成功.就打印輸出“査找成功”的信息，否則輸出“査找失畋”的信息。
10個(gè)C語(yǔ)言開(kāi)源項(xiàng)目代碼
1. Webbench
Webbench是一個(gè)在linux下使用的非常簡(jiǎn)單的網(wǎng)站壓測(cè)工具。它使用fork()模擬多個(gè)客戶端同時(shí)訪問(wèn)我們?cè)O(shè)定的URL，測(cè)試網(wǎng)站在壓力下工作的性能，最多可以模擬3萬(wàn)個(gè)并發(fā)連接去測(cè)試網(wǎng)站的負(fù)載能力。Webbench使用C語(yǔ)言編寫, 代碼實(shí)在太簡(jiǎn)潔，源碼加起來(lái)不到600行。下載鏈接：http://home.tiscali.cz/~cz210552/webbench.html
2. Tinyhttpd
tinyhttpd是一個(gè)超輕量型Http Server，使用C語(yǔ)言開(kāi)發(fā)，全部代碼只有502行(包括注釋)，附帶一個(gè)簡(jiǎn)單的Client，可以通過(guò)閱讀這段代碼理解一個(gè) Http Server 的本質(zhì)。下載鏈接：http://sourceforge.net/projects/tinyhttpd/
3. cJSON
cJSON是C語(yǔ)言中的一個(gè)JSON編解碼器，非常輕量級(jí)，C文件只有500多行，速度也非常理想。
cJSON也存在幾個(gè)弱點(diǎn)，雖然功能不是非常強(qiáng)大，但cJSON的小身板和速度是最值得贊賞的。其代碼被非常好地維護(hù)著，結(jié)構(gòu)也簡(jiǎn)單易懂，可以作為一個(gè)非常好的C語(yǔ)言項(xiàng)目進(jìn)行學(xué)習(xí)。項(xiàng)目主頁(yè):http://sourceforge.net/projects/cjson/
4. CMockery
cmockery是google發(fā)布的用于C單元測(cè)試的一個(gè)輕量級(jí)的框架。它很小巧，對(duì)其他開(kāi)源包沒(méi)有依賴，對(duì)被測(cè)試代碼侵入性小。cmockery的源代碼行數(shù)不到3K，你閱讀一下will_return和mock的源代碼就一目了然了。
主要特點(diǎn)：
免費(fèi)且開(kāi)源，google提供技術(shù)支持；
輕量級(jí)的框架，使測(cè)試更加快速簡(jiǎn)單；
避免使用復(fù)雜的編譯器特性，對(duì)老版本的編譯器來(lái)講，兼容性好;
并不強(qiáng)制要求待測(cè)代碼必須依賴C99標(biāo)準(zhǔn)，這一特性對(duì)許多嵌入式系統(tǒng)的開(kāi)發(fā)很有用
下載鏈接：http://code.google.com/p/cmockery/downloads/list
5. Libev
libev是一個(gè)開(kāi)源的事件驅(qū)動(dòng)庫(kù)，基于epoll，kqueue等OS提供的基礎(chǔ)設(shè)施。其以高效出名，它可以將IO事件，定時(shí)器，和信號(hào)統(tǒng)一起來(lái)，統(tǒng)一放在事件處理這一套框架下處理。基于Reactor模式，效率較高，并且代碼精簡(jiǎn)（4.15版本8000多行），是學(xué)習(xí)事件驅(qū)動(dòng)編程的很好的資源。下載鏈接：http://software.schmorp.de/pkg/libev.html
6. Memcached
Memcached 是一個(gè)高性能的分布式內(nèi)存對(duì)象緩存系統(tǒng)，用于動(dòng)態(tài)Web應(yīng)用以減輕數(shù)據(jù)庫(kù)負(fù)載。它通過(guò)在內(nèi)存中緩存數(shù)據(jù)和對(duì)象來(lái)減少讀取數(shù)據(jù)庫(kù)的次數(shù)，從而提供動(dòng)態(tài)數(shù)據(jù)庫(kù)驅(qū)動(dòng)網(wǎng)站的速度。Memcached 基于一個(gè)存儲(chǔ)鍵/值對(duì)的 hashmap。Memcached-1.4.7的代碼量還是可以接受的，只有10K行左右。下載地址：http://memcached.org/
7. Lua
Lua很棒，Lua是巴西人發(fā)明的，這些都令我不爽，但是還不至于臉紅，最多眼紅。
讓我臉紅的是Lua的源代碼，百分之一百的ANSI C，一點(diǎn)都不摻雜。在任何支持ANSI C編譯器的平臺(tái)上都可以輕松編譯通過(guò)。我試過(guò)，真是一點(diǎn)廢話都沒(méi)有。Lua的代碼數(shù)量足夠小，5.1.4僅僅1.5W行，去掉空白行和注釋估計(jì)能到1W行。下載地址：http://www.lua.org/
8. SQLite
SQLite是一個(gè)開(kāi)源的嵌入式關(guān)系數(shù)據(jù)庫(kù)，實(shí)現(xiàn)自包容、零配置、支持事務(wù)的SQL數(shù)據(jù)庫(kù)引擎。 其特點(diǎn)是高度便攜、使用方便、結(jié)構(gòu)緊湊、高效、可靠。足夠小，大致3萬(wàn)行C代碼，250K。 下載地址：http://www.sqlite.org/。
9. UNIX v6
UNIX V6 的內(nèi)核源代碼包括設(shè)備驅(qū)動(dòng)程序在內(nèi) 約有1 萬(wàn)行，這個(gè)數(shù)量的源代碼，初學(xué)者是能夠充分理解的。有一種說(shuō)法是一個(gè)人所能理解的代碼量上限為1 萬(wàn)行，UNIX V6的內(nèi)核源代碼從數(shù)量上看正好在這個(gè)范圍之內(nèi)。看到這里，大家是不是也有“如果只有1萬(wàn)行的話沒(méi)準(zhǔn)兒我也能學(xué)會(huì)”的想法呢？
另一方面，最近的操作系統(tǒng)，例如Linux 最新版的內(nèi)核源代碼據(jù)說(shuō)超過(guò)了1000 萬(wàn)行。就算不是初學(xué)者，想完全理解全部代碼基本上也是不可能的。下載地址：http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6
10. NETBSD
NetBSD是一個(gè)免費(fèi)的，具有高度移植性的 UNIX-like 操作系統(tǒng)，是現(xiàn)行可移植平臺(tái)最多的操作系統(tǒng)，可以在許多平臺(tái)上執(zhí)行，從 64bit alpha 服務(wù)器到手持設(shè)備和嵌入式設(shè)備。NetBSD計(jì)劃的口號(hào)是：”O(jiān)f course it runs NetBSD”。它設(shè)計(jì)簡(jiǎn)潔，代碼規(guī)范，擁有眾多先進(jìn)特性，使得它在業(yè)界和學(xué)術(shù)界廣受好評(píng)。由于簡(jiǎn)潔的設(shè)計(jì)和先進(jìn)的特征，使得它在生產(chǎn)和研究方面，都有卓越的表現(xiàn)，而且它也有受使用者支持的完整的源代碼。許多程序都可以很容易地通過(guò)NetBSD Packages Collection獲得。
【C語(yǔ)言二分查找折半查找算法及代碼】相關(guān)文章：
C語(yǔ)言快速排序算法及代碼06-25
10個(gè)經(jīng)典的C語(yǔ)言面試基礎(chǔ)算法及代碼03-14
C語(yǔ)言奇偶排序算法詳解及實(shí)例代碼04-05
C語(yǔ)言面試的10個(gè)經(jīng)典基礎(chǔ)算法及代碼01-04
C語(yǔ)言面試中10個(gè)經(jīng)典的基礎(chǔ)算法及代碼04-24
C語(yǔ)言字符串快速壓縮算法代碼02-19