? ? ? Hello,大家好，今天給大家繼續(xù)講解排序系列予跌〔可能有細心的"鳥友"會問，你不是講解排序嗎券册？怎么今天的主題是一個查找方法咧频轿？
? ? ? 不錯，因為考慮到在實際項目中烁焙，排序和查找經(jīng)常是兩個好基友航邢，二者息息相關(guān)，相互依存骄蝇。故為了大家更好的接手老板交給你的實際工作膳殷，而不至于被說成是"新兵蛋子"，我覺得大家有必要和我來學(xué)學(xué)這個查找法九火。
? ? ? ?言歸正傳赚窃，首先假定一個有序整數(shù)序列存儲在數(shù)組list[MAX]中,即list[0]<list[1]l<...<list[MAX-1];我們要查找的數(shù)為num_search令 1eft、 right分 別 表 示 表 中 待查序列的左右端 點 ,初 值 分別為:left=0,right=MAX-1岔激。再令 middle=(left+right)/2,為序列表 的 中間值 勒极。 num_search和 list[middle]比較的 結(jié)果 ,有三種可能 :
(1)num_search<list[middle].此 時 ,如 果 num_search在 表 中 ,它一定 在 位 置0與midde-1之間 ,因此 ,把 right設(shè)成 middle-1.
(2) num_search==list[middle]。 此 時 , middle所指位置就是要找的數(shù)虑鼎，函數(shù)返 回midd1e辱匿。
⑶ num_search>list[middle]。 此 時 ,如 果 searchnum在 表 中 ,它一定 在 位 置midde+1與MAX-1之間 ,因此 ,把 left設(shè) 成 middle+1.
為了程序的簡潔和兼容性，這種比較可以定義一個比較宏COMPARE(x,y)來實現(xiàn).
當 num_search還沒被找到,同時尚有沒檢查到的其它整數(shù),則我們重新計算 middle,重 復(fù)上述查找過程掀鹅。
? ? ? ? 接下來的程序是具體實現(xiàn)這種查找策略。程序?qū)崿F(xiàn)了由用戶自行設(shè)置序列個數(shù)LEN媒楼，然后由隨機數(shù)生成函數(shù)生成各元素乐尊，采用上節(jié)課講的選擇排序算法將序列轉(zhuǎn)換成由小至大排列的有序序列。
? ? ? ?最后就是今天的算法關(guān)鍵啦?《二分查找法》
? ? ? ?包括兩個子任務(wù):
(1)表中是否還有未查找過的整數(shù)
(2)比較 num_search和 list[middle]划址。
(3)遞歸調(diào)用
? ? ? 無圖無真相扔嵌！
