標題: [教學] 資料搜尋的技巧 (二分搜尋法 BinarySearch) [打印本頁] -------------------------------------------------------------------------------- 作者: yfchang 時間: 2008-7-25 02:13 標題: [教學] 資料搜尋的技巧 (二分搜尋法 BinarySearch) 版權宣告 本文內容可以讓非營利機關或個人進行非有償性教學, 或由學承電腦內講師採用, 唯請註明本文出處及原作者, 其他目的之使用請聯絡作者取得授權。 email : yfchang[at]cs.pu.edu.tw 出處請註明 網站: 學承電腦技術論壇 文章: 資料搜尋的技巧 (二分搜尋法 BinarySearch) 教學文件 作者: 學承電腦講師張演富 前言 在利用程式整理資料時, 常常會遇到搜尋的問題, 在這篇文章將要介紹一個搜尋方法--二分搜尋法 (Binary Search, 註1) 讓程式搜尋資料時能更有效率。 本教學文章為6/22 台中分校C++專業課程的補充文件, 以C++語言為實作例子。 註1：有人翻譯為"二元搜尋法"或是"二進位搜尋法", 筆者認為二分搜尋法較貼切方法本意。 線性搜尋法 (Linear Search) 首先, 以下是一個數列, 其中包含了已排序的八個數字, 0, 1, 3, 4, 6, 7, 9, 10 當程式需要檢驗 "6是否在這數列中" 一般最直接的方法就是從頭比較: 0!=6, 1!=6, 3!=6, 4!=6, 6=6 and found it (共比較五次才找到). 這樣從以一個順序的比較方法就稱為線性搜尋法(Linear Search)。 很顯然的, 當資料量大的時候, 整個搜尋的比較次數也會增大, 例如 當資料有一萬筆, 若所要的資料在最後一筆或找不到的時候, 就必須比較一萬次。我們將上述的數列中每一筆資料所需比較次數作成如下表： 從這表格中就可以推出當資料量為n 筆時, 它的平均比較次數就會是 (1+2+3+.....+n)/n = (n+1)/2 實際上這個技巧所花的比較次數是可以降低的, 就好像當我們查字典時, 不會從A找到Z, 而是會在大約的位置翻開, 查看所需的單字是在前方還是後方, 再逼近所需的頁面, "二分搜尋法"的精神就有點像這樣的方式。 二分搜尋法 (Binary Search) 二分搜尋法的基本精神就是比較數列中的中間資料的值, 根據其大小來判斷所搜尋的資料是在中間值的前半段或是後半段, 例如上述的例子搜尋7是否在 "0, 1, 3, 4, 6, 7, 9, 10" 的數列中, 首先會比較第 (1+8)/2=4 個的資料, 就是4, 而4<6 所以所要搜尋的資料在4的後半段, 因此, 所需搜尋的數列就縮小成 6 (index=5)~10 (index=8) [註2] 註2: 有些書上會把"4"放在後半或前半, 但是在縮小時還是應該要把它拿掉, 以節省比較次數。 另外在程式設計中, 索引值一般都是從0開始, 這個例子的索引值是從1開始, 這樣的差別是不影響計算的。 下一步就是比較第 (5+8)/2 = 6 個的資料, 就是7, 而7>6, 所以所要搜尋的資料在7的前半段, 因此, 所需搜尋的數列就縮小成 6 (index=5)~6 (index=5), 最後就找到所需的資料了。 由於這樣的方法在每個iteration (回合)會砍掉一半的資料, 因此也降低了比較的次數 iteration 1: 8/2 = 4 iteration 2: 4/2 = 2 iteration 3: 2/2 = 1 因為只有一筆資料, then found or not found. 所以這個case, 就是比較了三次。 我們將比較的流程以一個樹狀圖來表示如下, 當搜尋的值比節點內的值小時, 則走向左邊的節點, 反之則走向右邊, 整個樹形最深的位置也是只有經過四個節點的比較。 當數列量為n個時，其最差的比較次數就是log2n+1次, 若每個資料都以最差的情況計算, 則平均就是比較log2n+1次。 這個推法可能不是那麼的明顯, 其實樹形的深度是跟 log28 = 3 有關係 (2^3 =8 ) [註3] 註3: 有人將比較次數算做需要幾個回合, 意思就是要做幾次切分, 在這圖中最深需要過三個箭頭, 因此也有人算做 log2n。 和Linear Search 來比較, (n+1)/2 的增加速度是比 logn來的快很多, 如下圖紅色是線性的曲線 (y = (n+1)/2), 黑色的是log的曲線 (y = log2n), 整個增加的速度是差很多的, 因此對於大量的資料而言, Binary Search 會比Linear Search 來的有效率。 程式實作 數列的部份, 因為每一筆資料都是數字的格式, 因此我們用(data)陣列來儲存它。 請注意陣列中的索引值是以0為開始, 所以八筆資料的索引值為 0~7。 另外由於在每個回合必須將一段資料忽略, 所以再用start ,end 儲存目前所需搜尋的索引值區間 middle 儲存目前所需考慮的中間資料的索引值 ========== 程式碼開始 ============= int data[] = {0,1,3,4,6,7,9,10}; //資料數列 int start =0; //搜尋區間的起始索引值 int end = 7; //搜尋區間的結束索引值 int middle = (start + end)/2; //中間資料的索引值 int search = 6; //所要搜尋的資料, 假設搜尋6 while (data[middle]!= search){ if(data[middle]>search){ //當中間值比搜尋值大, 則搜尋資料在左半 end = middle-1; //將結束索引值指向中間值, 則下一回合的搜尋區間在前半段 } else { start = middle+1; //否則則在後半段, +/-1的作用在於把middle的資料忽略掉, 加快計算 } if(start>end){ //若起始值比結束還要大, 則表示資料中沒有搜尋的值 cout<<"Data "< middle = (start + end)/2; //更新middle 值 } if(!start>end){ //若索引值正常, 且while 迴圈正常結束, 則為match cout<<"data "< table.JPG (11.93 KB) 2008-7-25 02:13 s1.JPG (14.78 KB) 2008-7-25 02:13 s2.JPG (14.64 KB) 2008-7-25 02:13 s3.JPG (14.33 KB) 2008-7-25 02:13 log-linear.JPG (14.36 KB) 2008-7-25 02:54 decisiontree.JPG (8.43 KB) 2008-7-25 11:03 -------------------------------------------------------------------------------- 歡迎光臨 Pccenter技術論壇 (http://pforum.pccenter.com.tw/) Powered by Discuz! 5.5.0 資料搜尋字：http://pforum.pccenter.com.tw/redirect.php?tid=4521&goto=lastpost |
| 本站公告：〔您越需要我們，我們就越有創意〕 | 本站說明書：〔發現故鄉還有改進的地方，請來信告訴原丁們〕 |
| 觀察應用學習點數 ：〔咱的故鄉有您的參與，會使我們有更大的發揮空間，展現更豐富精彩的學習畫面〕 | 〔期待藉由無障礙網頁設計，能讓視障小朋友更愛看書、更愛寫作且更愛學習〕：盲用電腦「心得分享」 |