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