2-2 搜尋

一、搜尋簡介

• 搜尋（Search）是指在一群資料中尋找合乎某些特定條件的資料。

• 在日常生活中，「搜尋資料」是常有的經驗，例如：在學校的學生名單中，找出特定姓名的學生資料。

• 舉例來說，尋找陣列中的最大值或最小值，是日常生活中經常會遇到的問題。如果陣列內容已經依照大小順序排好，第一筆或最後一筆肯定就是最大值或最小值；但如果是沒有排序過的陣列，那該怎麼辦？

• 如果要從沿路的若干顆珍珠找出一顆最大的珍珠。

• 首先將眼前看到的第一顆珍珠A 放入袋中，接著從之後遇到的第二顆珍珠B開始逐一檢查比較。

• 如果正在檢查的B 比袋中的A 還大，則將B撿起放入袋中，置換取代原先袋中的A。

• 反之，則仍繼續以袋中的珍珠A比較沿路逐一遇到的每一顆珍珠C、D⋯⋯。

二、常見的搜尋演算法

1. 循序搜尋法

• 循序搜尋法（Sequential Search）又稱為線性搜尋法（Linear Search），是一種很容易理解，但搜尋效率比較差的方法。

• 「循序搜尋法」搜尋資料時，會由前往後（或由後往前）依序逐一比對各資料項，直到「找到想要搜尋的資料項」或「全部資料項都比對完畢，但確定沒找到」為止。

• 循序搜尋法－實作方式

有一資料列，內容分別為 2、5、7、4、9、3、1、8（共八項）。若要尋找資料「7」：由前往後逐一比對，找到第三項就完成了。

進階練習

下面是星星相印電影院在本周的每日售票情形，我們的任務是使用循序搜尋法，找出本周最大的售票數量是多少？是在星期幾？

• 二分搜尋法的符號定義

‧ 資料列（假設順序已經由小而大排列）

‧ 共有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」的過程如下：

實作方式(4)

因為 11=A[6]，表示搜尋完成，如果不相等則表示找不到，搜尋結束。

實作演練-答案

第一次：

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，表示找不到，搜尋結束。