08年9月入學(xué)，12年7月畢業(yè)，結(jié)束了我在軟件學(xué)院愉快豐富的大學(xué)生活。此系列是對(duì)四年專(zhuān)業(yè)課程學(xué)習(xí)的回顧，索引參見(jiàn)：http://blog.csdn.net/xiaowei_cqu/article/details/7747205

查找算法

查找算法是在存在的序列（list） 中查找特定的目標(biāo)（target），要求序列中每個(gè)記錄必須與一個(gè)關(guān)鍵詞（key）關(guān)聯(lián)才能進(jìn)行查找。
查找算法通常需要兩個(gè)輸入： 1、被查找的序列 2、要查找的關(guān)鍵詞 查找算法的輸出參數(shù)和返回值： 1、返回類(lèi)型為?Error_code 的值用以表示是否查找成功 2、如果查找成功，返回 success， 輸出參數(shù) position 定位到目標(biāo)所在位置 3、如果查找失敗，返回?not present，輸出參數(shù)可能是未定義或不同于已有位置的任何值

順序查找算法

順序查找算法的思路很簡(jiǎn)單：從表的第一個(gè)元素開(kāi)始一個(gè)一個(gè)向下查找，如果有和目標(biāo)一致的元素，查找成功；如果到最后一個(gè)元素仍沒(méi)有目標(biāo)元素，則查找失敗。

【實(shí)驗(yàn)說(shuō)明】

題目：編寫(xiě)一個(gè)程序，對(duì)順序表{3,6,2,10,1,8,5,7,4,9},采用順序查找關(guān)鍵字5的過(guò)程。要求輸出：
1）原順序表；2）查找到關(guān)鍵字的位置；3）進(jìn)行比較的次數(shù)。
1.首先要編寫(xiě)類(lèi)表List。需要滿(mǎn)足最基本的操作插入insert（），獲取retrieve（），以及得到大小size（）。
2.我們觀察題目要求，表中雖然存儲(chǔ)的是簡(jiǎn)單的整數(shù)，但如果我們使用List<int>對(duì)象顯然無(wú)法記錄比較次數(shù)，所以我們自己寫(xiě)一個(gè)類(lèi)Key通過(guò)其內(nèi)部int類(lèi)型的數(shù)據(jù)成員來(lái)記錄存于表中的值，并模仿int基本的邏輯操作，即編寫(xiě)重載邏輯運(yùn)算符，同時(shí)增加一個(gè)靜態(tài)數(shù)據(jù)成員comparisons用于記錄其比較操作的次數(shù)。
3.準(zhǔn)備工作做好之后開(kāi)始編寫(xiě)順序查找算法。算法的思路很簡(jiǎn)單，也較易實(shí)現(xiàn)，從表中第一個(gè)元素開(kāi)始比較，發(fā)現(xiàn)目標(biāo)則返回元素所在表中位置；若遍歷之后沒(méi)有目標(biāo)，則查找失敗，返回-1表示表中沒(méi)有目標(biāo)元素。 4.按題目要求編寫(xiě)最后的輸出函數(shù)。

【相關(guān)代碼】

函數(shù)?sequential_search [cpp]?view plaincopy

int?sequential_search(const?List<int>?&the_list,??

??????????????????????const?Key?&target)??

/*Post:?If?an?entry?in?the_list?is?equal?to?target,?then?return?the?position?

????????of?this?entry.??

????????Otherwise?return?-1??

*/??

{??

????int?position;??

????int?s=the_list.size();??

????for(position=0;position<s;position++){??

????????int?data;??

????????the_list.retrieve(position,data);??

????????if(data==target){??

????????????return?position;??

????????}??

????}??

????return?-1;??

}??

二分查找算法

二分查找前提是表是按遞增或遞減順序的規(guī)范表。此次實(shí)驗(yàn)中我們使用的是遞增表。
二分查找從表中間開(kāi)始查找目標(biāo)元素。如果找到一致元素，則查找成功。如果中間元素比目標(biāo)元素小，則仍用二分查找方法查找表的后半部分（表是遞增排列的），反之中間元素比目標(biāo)元素大，則查找表的前半部分。

【實(shí)驗(yàn)說(shuō)明】

題目：編寫(xiě)一個(gè)程序，對(duì)有序表{1,2,3,4,5,6,7,8,9,10},采用二分查找關(guān)鍵字9的過(guò)程。要求輸出：
1）原順序表；2）查找到關(guān)鍵字的位置；3）進(jìn)行比較的次數(shù)。
1.二分查找算法的前提是表必須是有序的，如題目中是遞增方式排列的表。實(shí)現(xiàn)表的有序一方面是用戶(hù)規(guī)范輸入，另一方面我們也可以編寫(xiě)有序的類(lèi)來(lái)方便用戶(hù)的輸入。
所以從List中派生類(lèi)Oredered_list，重新編寫(xiě)函數(shù)Error_code insert（int position，const Record &data），使插入的位置不滿(mǎn)足表的有序條件時(shí)，不能插入。
同時(shí)編寫(xiě)插入的重載函數(shù) Error_code insert(const Record &data)，可以直接插入到合適的位置，方便用戶(hù)輸入。
2.仍使用題目1中的Key來(lái)表示目標(biāo)
3.實(shí)現(xiàn)二分查找算法。通過(guò)書(shū)中的學(xué)習(xí)，我們直接使用添加相等判斷的二分查找算法。即每次從表的中間元素開(kāi)始比較，如果得到目標(biāo)則返回元素所在表中位置；如果中間元素小于目標(biāo)元素，則對(duì)右半部分繼續(xù)二分查找；反之對(duì)前半部分表進(jìn)行二分查找。若最后都沒(méi)有目標(biāo)元素，返回-1用以表示表中沒(méi)有目標(biāo)元素。
4.仍使用題目1編寫(xiě)的輸出函數(shù)將結(jié)果輸出。
/*注意這里因?yàn)镺rdered_list是從List中派生而來(lái)，所以雖然print_out函數(shù)中第一個(gè)參數(shù)類(lèi)型是List<int>，仍可以使用，而不用編寫(xiě)重載函數(shù)*/

【相關(guān)代碼】

函數(shù)?binary_search [cpp]?view plaincopy

int?binary_search(const?Ordered_list<int>?&the_list,??

????????????????????const?Key?&target)??

/*Post:?If?an?entry?in?the_list?is?equal?to?target,?then?return?the?position?

????????of?this?entry.??

????????Otherwise?return?-1??

*/??

{??

????int?position;??

????int?data;??

????int?bottom=0,top=the_list.size()-1;??

????while(bottom<=top){??

????????position=(bottom+top)>>1;???

????????the_list.retrieve(position,data);??

????????if(data==target)??

????????????return?position;??

????????if(data<target)bottom=position+1;??

????????else?top=position-1;??

????}??

????return?-1;??

}??

【過(guò)程記錄】

實(shí)驗(yàn)截圖：

【結(jié)果分析】

A.實(shí)現(xiàn)順序查找算法

1.順序查找算法思路很簡(jiǎn)單，就是一種遍歷的思想，一個(gè)個(gè)查找目標(biāo)元素，實(shí)現(xiàn)也很簡(jiǎn)單。
2.對(duì)于有n個(gè)元素的表適用順序查找。比較次數(shù)：不成功：比較n次。成功查找：最好的情況為1次，即第一個(gè)元素即為目標(biāo)元素；最差的情況為n次；平均比較次數(shù)（n+1）/2次。
所以當(dāng)表很大時(shí)，順序查找的代價(jià)是很大的。
3.順序查找算法不會(huì)有重復(fù)的比較出現(xiàn)，即一旦找到即成功，但同時(shí)這種代價(jià)是當(dāng)表中有重復(fù)的目標(biāo)元素時(shí)（比如有多個(gè)目標(biāo)元素）我們只能得到第一個(gè)元素的位置。

B.實(shí)現(xiàn)二分查找算法

1.二分查找法思路：遞增排列的表，首先從中間元素開(kāi)始查找，如果元素比目標(biāo)元素小，則查找后半部分表，反之查找前半部分表，并重復(fù)這一過(guò)程。這樣每次查找中我們都把表的長(zhǎng)度減半。
2.二分查找在實(shí)現(xiàn)中有量bottom和top，每次減半的過(guò)程體現(xiàn)在bottom和top的改變上，在代碼的實(shí)現(xiàn)上可以使用單純的循環(huán)或者用函數(shù)遞歸的思想。
遞歸思想更容易理解，但編寫(xiě)之后我們發(fā)現(xiàn)函數(shù)是尾遞歸，尾遞歸通常可以用簡(jiǎn)單的循環(huán)實(shí)現(xiàn)，循環(huán)在操作來(lái)說(shuō)沒(méi)有了函數(shù)調(diào)用的過(guò)程，更節(jié)省時(shí)間和空間。
3.編碼中小小地方的改動(dòng)可能對(duì)程序有很大的改觀。
如上述兩種二分查找binary_search_1（不比較等于的情況）binary_search_2（添加等于情況）

實(shí)驗(yàn)代碼下載：http://download.csdn.net/detail/xiaowei_cqu/4437702

（轉(zhuǎn)載請(qǐng)注明作者和出處：http://blog.csdn.net/xiaowei_cqu?未經(jīng)允許請(qǐng)勿用于商業(yè)用途）

總結(jié)

以上是生活随笔為你收集整理的查找算法：二分查找、顺序查找的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。