一、搜尋簡介
搜尋(Search)是指在一群資料中尋找合乎某些特定條件的資料。
在日常生活中,「搜尋資料」是常有的經驗,例如:在學校的學生名單中,找出特定姓名的學生資料。
舉例來說,尋找陣列中的最大值或最小值,是日常生活中經常會遇到的問題。如果陣列內容已經依照大小順序排好,第一筆或最後一筆肯定就是最大值或最小值;但如果是沒有排序過的陣列,那該怎麼辦?
如果要從沿路的若干顆珍珠找出一顆最大的珍珠。
首先將眼前看到的第一顆珍珠A 放入袋中,接著從之後遇到的第二顆珍珠B開始逐一檢查比較。
如果正在檢查的B 比袋中的A 還大,則將B撿起放入袋中,置換取代原先袋中的A。
反之,則仍繼續以袋中的珍珠A比較沿路逐一遇到的每一顆珍珠C、D⋯⋯。
二、常見的搜尋演算法
循序搜尋法(Sequential Search)又稱為線性搜尋法(Linear Search),是一種很容易理解,但搜尋效率比較差的方法。
「循序搜尋法」搜尋資料時,會由前往後(或由後往前)依序逐一比對各資料項,直到「找到想要搜尋的資料項」或「全部資料項都比對完畢,但確定沒找到」為止。
循序搜尋法-實作方式
有一資料列,內容分別為 2、5、7、4、9、3、1、8(共八項)。若要尋找資料「7」:由前往後逐一比對,找到第三項就完成了。
若要尋找資料「3」:由前往後逐一比對,要找到第六項才完成。
若要尋找資料「6」:全部八項資料都比對完畢,最後沒有找到才結束。
下面是星星相印電影院在本周的每日售票情形,我們的任務是使用循序搜尋法,找出本周最大的售票數量是多少?是在星期幾?
先建立一個「每日售票數」的清單,並將數字依星期日、星期一、…、星期六的順序加入清單中。
建立「清單位置」、「最大值位置」及「星期」等三變數,以記錄由清單中逐一比對出的最大值的序位,並以序位轉換成星期幾。
完成循序搜尋的程式如右
接下來利用條件判斷將最大位置轉成星期幾
最後顯示出搜尋的結果
2. 二分搜尋法
適用於已經依大小順序排列的資料列,如果有一串由小而大順序排列的數列,就可以先將資料列分割成兩等份,再比較欲搜尋資料與中間項的大小關係,規則如下:
(1) 若欲搜尋之資料恰等於中間項:中間項即為欲搜尋資料,搜尋結束。
(2) 若欲搜尋之資料小於中間項:要找的資料應該在前半段,繼續往前半段搜尋。
(3) 若欲搜尋之資料大於中間項:要找的資料應該在後半段,繼續往後半段搜尋。
(4) 依此類推,如此分割數次直到找到欲搜尋資料或確定欲搜尋資料不存在為止。
二分搜尋法的符號定義
‧ 資料列(假設順序已經由小而大排列)
‧ 共有n項
‧ 搜尋範圍區域內的首項為第L項,末項為第R項,L<R
‧ 中間項為第M項
‧ M=(L+R)/2(取整數部分)
二分搜尋法的步驟
(1) 一開始的搜尋區域是資料列全部,因此首項L=1,末項R=n。
(2) 如果L>R,表示資料列已經全部找過但沒找到,則搜尋結束。否則M=(L+R)/2,繼續搜尋比較。
(3) 比較欲搜尋資料與中間項M的內容值
(a) 如果欲搜尋資料=中間項M的內容值,表示順利找到,則搜尋完成。
(b) 如果欲搜尋資料>中間項M的內容值,則繼續往後半部分重新搜尋,此時新首項L=M+1,回到步驟2。
(c) 如果欲搜尋資料<中間項M的內容值,則繼續往前半部分重新搜尋,此時新末項R=M-1,回到步驟2。
註:若「L+R」為偶數,則M恰為整數。若「L+R」為奇數,則M取整數部分,小數部分不計。
二分搜尋法-實作方式
有一串已經依照由小而大順序排列的資料陣列A,內容為2、3、5、8、9、11、13、16、18,而所要搜尋值為「11」的過程如下:
實作方式(1)
首先跟第五項(L=1、R=9、M=(1+9)/2 = 5)數值「9」比較:
實作方式(2)
因為11>A[5],所以再和後半部(L=5+1=6、R=9)的中間項(第七項:M=(6+9)/2=7.5→7)數值「13」比較:
實作方式(3)
因為 11<A[7],所以再和原後半部的前半部(L=6、R=7-1=6)中間項(第六項:M=(6+6)/2=6)數值「11」比較:
實作方式(4)
因為 11=A[6],表示搜尋完成,如果不相等則表示找不到,搜尋結束。
實作演練
上例中,如果欲搜尋值分別為5 與12,請試著採用二分搜尋法並紀錄搜尋過程。
實作演練-答案
第一次:
L=1,R=9,M=(1+9)/2=5
首先跟A[5](數值「9」)比較,因為 5<9,所以需再往前半部比較。
第二次:
L=1,R=5,M=(1+5)/2=3
接著跟A[3](數值「5」)比較,因為 5=5,所以表示搜尋完成。
實作演練
上例中,如果欲搜尋值分別為5 與12,請試著採用二分搜尋法並紀錄搜尋過程。
實作演練-答案
第一次:
L=1,R=9,M=(1+9)/2=5
首先跟A[5](數值「9」)比較,因為 12>9,所以需再往後半部比較。
第二次:
L=5,R=9,M=(5+9)/2=7
接著跟A[7](數值「13」)比較,因為 12<13,所以需再往剩餘部分的前半部比較。
第三次:
L=5,R=7,M=(5+7)/2=6
接著跟A[6](數值「11」)比較,因為 12≠11,表示找不到,搜尋結束。