第 九 章 搜尋(Search) 課程名稱：資料結構 授課老師：_____________.

Presentation on theme: "第 九 章 搜尋(Search) 課程名稱：資料結構 授課老師：_____________."— Presentation transcript:

1 第 九 章 搜尋(Search) 課程名稱：資料結構 授課老師：_____________

2 本章學習目標 1.讓讀者了解搜尋的意義與分類。 2.讓讀者了解搜尋的各種方法及適用時機。

3 本章內容 9-1 搜尋(Search) 9-2 循序搜尋法(Sequential Search)
9-3 二分搜尋法(Binary Search) 9-4 二元樹搜尋法(Tree Search) 9-5 內插搜尋法(Interpolation Search) 9-6 雜湊搜尋法(Hashing Search)

4 9-1 搜尋(Search) 【定義】 就是在一群資料中找尋所要的特定資料。當資料量很龐大時， 如何快速搜尋到資料是本章所要探討的重點。
【分類】若依資料量大小來區分，搜尋可分兩類： 1.內部搜尋 2.外部搜尋

5 1.內部搜尋 【定義】欲找尋的資料量較小時，可以直接全部載入記憶體中來進行 搜尋的動作。 【適用時機】資料量較少者。 【圖解】 資料量較少
全部一次載入 主記憶體

6 2.外部搜尋 【定義】若要找尋的資料量較大時，無法一次將全部內容置於主記憶體 內，而需使用到外部的輔助記憶體來分批處理。
【適用時機】資料量較大者。 【圖解】 無法一次載入 資料量較大 主記憶體 輔助記憶體

7 資料結構課程中的「搜尋」方法 一般而言，在資料結構課程中，常見的有「循序搜尋」、「二分搜尋」、「二元樹搜尋」及「雜湊搜尋」四種搜尋方法，因此，在本章節中將依序的介紹。

8 9-2 循序搜尋法 (Sequential Search)
【定義】 從第一個資料項開始依序取出與「目的資料項(鍵值Key)」相互比較， 直到找出所要的元素或所有資料均已找完為止，這種搜尋法稱為「循 序搜尋」。 【優點】1.程式容易撰寫。 2.資料不須事先排序。 【缺點】搜尋效率較差(平均次數= )，因為不管資料順序為何，每次 都必須要從頭到尾拜訪一次。

9 【演算法】

10 【時間複雜度之分析】 如果資料沒有重覆，找到資料就可中止搜尋的話，在最差狀況是未找到資料，需作n次比較，時間複雜度為O(n)。
所以，平均時間與最差時間為O(n)，最佳時間為O(1)

11 9-3 二分搜尋法(Binary Search)
【定義】 先將資料分割成兩部份，再利用「鍵值」與「中間值」來比較大小， 如果鍵值小於中間值，則可確定要找的資料在前半段的元素中，如 此分割數次直到找到為止。 【圖解】 【適用時機】事先已經排序完成。 【優點】搜尋效率較佳(平均次數=Log2N)。 【缺點】1.資料必須事先排序。 2.檔案必須是直接存取檔或隨機檔

12 【演算法】 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 Procedure binsearch(A[], key , low, high) Begin if(low<=high) //第一項資料的索引 值小於最後一項資料的索引值 { mid= ; //計算中間值的位置 switch compare(key, A[mid]) //「鍵值」與「中間值」比較大小 Case "=": return mid; //找到 Case “<”: return binsearch(A, key, low, mid-1) ; //遞迴呼叫找左半部 Case ">": return binsearch(A, key, mid+1, high) ; //遞迴呼叫找右半部 } Return -1; //搜尋失敗，傳回-1 End End Procedure

13 【時間複雜度之分析】

14 【作法】 步驟 將所有資料由小至大排序。 步驟 設L(Low)表示第一項資料(最小)的索引，
H(High)表示最後一項資料(最大)的索引。 步驟 M(Middle)表示中間項的索引＝ 步驟 將「鍵值 」和「中間值」做比較。 當鍵值 ＞中間值 ，則L＝M＋1。 當鍵值 ＜中間值 ，則H＝M－1。 當鍵值 ＝中間值 ，則表示已經找到。 步驟重新計算M(中間值之索引)之後，再重複步驟和， 直到找到或所有資料均找過為止。

15 【實例】 假設有九筆資料：8,1,99,76,88,45,15,33,24 現在我們想從資料中尋找「88」，請利用二分搜尋法來進行搜尋，並撰寫出完整的步驟。 【解答】 步驟 將所有資料由小至大排序之後，並依序存入一維陣列中。 1, 8, 15, 24, 33, 45, 76, 88, 99 步驟 設L(Low)表示第一項資料(最小) 的索引， H(High)表示最後一項資料(最大) 的索引。 已知：L=0, H=8 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99

16 步驟 計算M(Middle)表示中間值的索引＝
由於L=0, H=8，所以代入公式M= M= =4 步驟 將「鍵值」和「中間值」做比較。 假設鍵值Key=88 因為，Key=88>A[4]=33，所以 當鍵值＞中間值，所以，欲尋找的資料在右半邊， 因此，重新計算L＝M＋1=4+1=5 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 忽略不理 鍵值在右邊

17 步驟 重新計算M(中間值之索引)，重複步驟和， 直到找到或所有資料均找過為止。
因為，Key=88>A[6]=76，所以 當鍵值＞中間值， 所以，欲尋找的資料在右半邊， 因此，重新計算L＝M＋1=6+1=7 M= =7 因為，Key=88=A[7]，所以找尋成功。 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 忽略不理 鍵值在右邊 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 1 8 15 24 33 45 76 88 99 忽略不理 忽略不理 鍵值在右邊

18 【比較循序搜尋法與二分搜尋法 】

19 9-4 二元樹搜尋法(Binary Search)
【定義】 二元樹搜尋法是先將資料列建立成為一棵二元搜尋樹，樹中的每一節 點資料一定會大於它的左子樹，而小於它的右子樹，亦即左子樹的值 ≦樹根的值≦右子樹的值。 【優點】1.插入與刪除時，只須改變少數指標。 2.二元樹搜尋效率較高(介於循序法與二分法之間) 【缺點】1.有左、右二指標欄，需要較大的記憶體空間。 2.資料必須事先排序。 【時間複雜度】最差時間O(n)、平均時間O(log2n)及最佳時間O(1)

20 【建立二元搜尋樹】 1. 依照資料輸入順序來建立 2. 第一個輸入的資料(數)當作樹根 3. 接下來輸入的數從樹根的節點資料開始與之相比
4. 如果比樹根的節點資料大，則再和其右子樹相比（如果沒有右子樹， 就將新輸入的數當作其右子樹） 5. 如果比樹根的節點資料小，就再和其左子樹相比（如果沒有左子樹， 就將新輸入的數當作其左子樹） 6. 遞迴執行前二步驟直到位置確定 7. 重複前四步驟直到資料輸入結束 註：請參考ch6-5二元搜尋樹之建立方法。

21 【二元樹搜尋之作法】 「樹根鍵值」，則放棄右子樹，只針對左子數來進行搜尋即可。 步驟一：將「搜尋鍵值」與「樹根鍵值」比較，若兩者相同時，則
搜尋成功，程式結束。 步驟二：若「搜尋鍵值」大於「樹根鍵值」，則放棄左子樹，只針 對右子數來進行搜尋即可。反之，若「搜尋鍵值」小於 「樹根鍵值」，則放棄右子樹，只針對左子數來進行搜尋即可。 步驟三：若尚未找到欲搜尋的資料，則重複執行前面兩個步驟，直 到左、右子樹全部比對完畢為止，表示未找到搜尋值，則 搜尋失敗，程式結束。

22 【舉例】 假設在陣列A中存入5, 7, 9, 2, 1,4等6個數值資料，並且建立成二元搜尋樹，請利用二元樹尋法來找尋數值4，必須要比較多少次？ 【解答】 前置工作：建立成二元搜尋樹

23 步驟一：將搜尋值與樹根的鍵值比較開始。 ∵搜尋值4＜樹根5 ∴搜尋尚未成功。因此，繼續執行下一個步驟。 步驟二：因為搜尋值小於樹根值，則放棄右子樹，只針對左子數來 進行搜尋即可。所以，分別與5、2及4比較，因此，共比 較了3次。

24 9-5 內插搜尋法 (Interpolation Search)
【定義】 內插搜尋法又叫做插補搜尋法，是二元搜尋法的改良版。它是依 照資料位置的分佈，利用公式預測資料的所在位置，再利用二分法 的方式漸漸逼近。 【例如】 我們在查詢英文字典時，當要查詢「book」單字時，則通常會 先翻到開頭是「b」的英文字，然後逐步往前或往後尋找。

25 【作法】 假設有n筆記錄K1,K2,K3,…,Kn，欲從中找尋Kmid(中間值)使得其對應的鍵值Kmid=key，其中 K1 ≦ K2 ≦ K3 ≦… Kmid ≦… ≦ Kn ，因此，每次都必須將Kmid和key做比較,再調整下次mid的值. 轉換成程式碼，如下所示： mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low ) 其中：low與high分別用來設定目前搜尋範圍的左右邊界位置 【圖解】

26 【舉例】假設有A,B兩串數列，如下所示： A數列： 9，14，20，25，30，36，42，48，53 B數列： 9，10，12，24，30，31，33，35，37，40 此時，如何分析A,B兩串數列的分佈情況？ 【分析】 (A)數列兩兩差距為5或6，即很接近，近似均勻分佈 (B)數列兩兩差距有1，2，6，12，資料集中在30~40範圍，為不均勻 分佈。

27 【演算法】 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 Procedure IntSearch(data[ ], key, n) Begin low=0; high=n-1; //low與high分別用來設定目前搜尋範圍的左右邊界位置 while(low <= high) //如果左邊界位置小於等於右邊界位置時，則 { //調整mid的值 mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low ) if(mid < low || mid > high) //超過範圍 return -1; //傳回-1(即代表搜尋失敗) if(key < data[mid]) //如果鍵值比中間值小,則必須要調整high之值 high = mid - 1; //右邊界位置=中間位置-1 else if(key > data[mid]) //如果鍵值比中間值大,則必須要調整low之值 low = mid + 1; //左邊界位置=中間位置+1 else //否則，代表已經找到鍵值的位置 return mid; //此時，傳回中間索引值的位置 } return -1; //搜尋失敗，傳回-1 End End Procedure

28 【時間複雜度】 1.最佳時間：O(1) 2.平均時間： O(log n) 3.最差時間： O(log n) 【適用時機】資料分佈均勻時，搜尋速度極快

29 【內插搜尋法深入探討】 1.一般而言，內插搜尋法優於循序搜尋法，而如果資料的分佈愈平
均，則搜尋速度愈快，甚至可能第一次就找到資料。因此，內插 搜尋法的時間複雜度取決於資料分佈的情況而定，平均而言優於 O(log n)。 2.使用內插搜尋法資料需先經過排序。

30 【內插搜尋法的步驟】 假設有n筆資料，內插搜尋法的步驟如下： 其中: key是要尋找的鍵 data[high]：是剩餘待尋找記錄中的最大值
data[low]：是剩餘待尋找記錄中的最小值 步驟1.將記錄由小到大的順序給予1,2,3...n的編號 步驟2.令low=1，high=n 步驟3.當low<high時，重複執行步驟4及步驟5 步驟4.令Mid=low + (( key - data[low] ) / ( data[high] – data[low] ))* ( high - low ) 步驟5. (1)若data[Mid]>key且high≠Mid-1則令high=Mid-1 (2)若data[Mid]＝key表示成功搜尋到鍵值的位置 (3)若data[Mid]<key且low≠Mid+1則令low=Mid+1

31 【範例】利用內插搜尋法，對下列資料搜尋50 【解答】 (1) low=0,high=9
由mid=low+(key-A[low]) /(A[high]-A[low]) *(high-low) 得知mid=0+(50-1) /(100-1) *(9-0)=49/99*9 ≒ 4 所以mid=4,A[4]=38<50 所以low=mid+1=4+1=5 (2) low=5,high=9 所以mid=5+(50-44) /(100-44) *(9-5)=5+6/56*4 ≒ 5 比較A[5]=44<50 所以low=mid+1=6 (3)low=6,high=9 所以mid=6+(50-46) /(100-46) *(9-6) ≒6 比較A[6]=46<50 所以low=mid+1=6+1=7 (4) low=7,high=9 所以mid=7+(50-50) /(100-50) *(9-7) ≒7 比較A[7]=50, 所以搜尋成功, 序列A中,A[7]=50 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] 1 3 15 27 38 44 46 50 58 100

32 9-6 雜湊搜尋法 (Hashing Search)
【定義】 指資料在存取時，是透過某種特定的數學函數，以轉換成鍵值(Key Value)資料的儲存位址。這種求算位址的方法叫做雜湊法(Hashing)。如下圖所示：

33 【優點】 (1)搜尋速度最快。 (2)資料不須事先排序 ( sorting ) 。
(3)在沒有碰撞 ( collision ) 及溢位 ( overflow ) 的情形下，只需一次即 可讀取。 (4)搜尋的速度與資料量大小無關。 (5)保密性高，若不知雜湊函數，無法擷取到資料。 (6)可做資料的壓縮 ( data compression ) ，利用適當的雜湊函數，可 將資料壓縮到一個較小的範圍內，以節省空間。

34 【缺點】 (1)浪費空間(因為有溢位區)，儲存空間的利用率比循序檔差。
(2)若有碰撞問題(Collision)發生時，則會嚴重影響存取速度。 (3)程式設計比較複雜。 (4)大量資料無效率(因為會產生碰撞問題(Collision))。 (5)不適合循序型的媒體。如磁帶。

35 9-6.1 雜湊函數 ( hashing function )
1.桶 ( bucket ) 雜湊表中儲存資料的位置，每個位置被給定一個唯一的位址，稱之為 bucket address 。 2.槽 ( slot ) 每一個桶可能有好幾個儲存區，此儲存區便稱之為槽 ( slot ) 。每一 個槽可以容納一個記錄。 3.碰撞 ( collision ) 當兩個不同的鍵值經過雜湊函數運算後，落在相同的 bucket address ，稱之為碰撞。 4.溢位 ( overflow ) 如果一個鍵值經過雜湊函數運算後，所對應的 bucket 已經滿了， 就稱之為溢位。

36 一般常見的雜湊函數有下列幾種方法： 1. 中間平方法 ( mid - square ) 2. 折疊法 ( folding )
3. 除法 ( Division ) 4. 數字分析法 ( digit analysis )

37 1. 中間平方法 ( mid - square ) 【定義】是指將鍵值平方後，取出中間某些位元來當作資料儲存的位址。 【例如】我們可以利用中間平方法將英文字的「ABC」轉換為雜湊表 中的位置。如下圖所示。

38 2. 折疊法 ( folding ) 【定義】是指將鍵值分為數段，除了最後一段外，其餘各段皆須等長，
然後將每一段相加，即可得到其所對應的位址。 【分類】 (1)位移折疊 ( shift folding ) (2)邊界折疊 ( folding at the boundaries )

39 (1) 位移折疊 ( shift folding )
【定義】是指將鍵值分為數段之後，再將各段資料直接相加。 【範例】假設有一個鍵值為 ，其儲存位址為何？ 【解答】 假設將其切割成 5 段，如下所示： 123 203 241 112 205

40 (2) 邊界折疊 ( folding at the boundaries )
【定義】將奇數位段或偶數位段反轉後相加。 【範例】假設有一個鍵值為 ，請利用「偶數位段」 求其儲存位址為何？ 【解答】 假設將其切割成 5 段，如下所示： 123 203 241 112 205 (203反轉) (112反轉)

41 3. 除法 ( Division ) 【定義】 此法利用Mod運算，將鍵值 X 除以某一個數值 M ，取其餘數當做 X 的位址。這個位址介於 0 ~ M-1 之間。而在使用除法時，一般建議利用質數會有較佳的效果。 【除法公式】 H( X ) = X mod M 其中： X代表某一鍵值 M代表某一質數 H(X)代表取其餘數當做 X 的位址

42 3. 除法 ( Division )(續) 【範例】 假設有一串鍵值X分別為：15,29,52,100,200，並且M設為13，請問如何求出鍵值X的儲存位址？ 【解答】 X H(X) 位址 資料 15 29 52 100 200 X MOD 13 1 2 3 4 5 6 7 8 9

43 4. 數字分析法 ( digit analysis )
數字分析法有二種： (1)觀察數字分析法： 利用觀察法，將鍵值分佈不平均的數字刪除，其餘保留為雜湊位址。 (2)統計數字分析法： 利用統計方法分析鍵值各位數的分析情形，求出雜湊位址。

44 (1)觀察數字分析法： 【範例】假設有5位同學，其學號共有五位數(N1,N2,N3,N4,N5)， 分別為： S1_No：98123
將以上五位同學的學號列表如右： 桶址 學號 N1 N2 N3 N4 N5 98123 9 8 1 2 3 98089 98563 5 6 99073 7 99429 4

45 如果我們使用「觀察數字分析法」來觀察上面表格，可以得知： N1桶址中的數字：只有9 N2桶址中的數字：只有8與9
學號 N1 N2 N3 N4 N5 98123 9 8 1 2 3 98089 98563 5 6 99073 7 99429 4 如果我們使用「觀察數字分析法」來觀察上面表格，可以得知： N1桶址中的數字：只有9 N2桶址中的數字：只有8與9 N1及N2桶址中的數字分佈比較不平均(不被取用) N3、N4及N5桶址中的數字分佈比較平均(被取用) 雖然我們可以選出N3、N4及N5中的2個桶址來使用，但是利用「觀察數字分析法」無法保證是最佳的選擇，並且沒有科學，因此，我們可以利用「統計數字分析法」。

46 (2)統計數字分析法： 【範例】假設有5位同學，其學號共有五位數(N1,N2,N3,N4,N5)， 分別為： S1_No：98123
將以上五位同學的學號列表如右上方： 出現次數 桶址 1 2 3 4 5 6 7 8 9 N1 N2 N3 N4 N5 桶址 學號 N1 N2 N3 N4 N5 98123 9 8 1 2 3 98089 98563 5 6 99073 7 99429 4

47 其中：Ski：代表N1到N5的分佈曲度，Ait代表Ni出現t的次數。
出現次數 桶址 1 2 3 4 5 6 7 8 9 N1 N2 N3 N4 N5 從上表中，我們可以利用公式： ， 其中：Ski：代表N1到N5的分佈曲度，Ait代表Ni出現t的次數。 SK1=|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|5-1|=13 SK2=|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|3-1|+|2-1|=11 SK3=|2-1|+|1-1|+|0-1|+|0-1|+|1-1|+|1-1|+|0-1|+|0-1|+|0-1|+|0-1|=7 SK4=|0-1|+|0-1|+|2-1|+|0-1|+|0-1|+|0-1|+|1-1|+|1-1|+|1-1|+|0-1|=7 SK5=|0-1|+|0-1|+|0-1|+|3-1|+|0-1|+|0-1|+|0-1|+|0-1|+|0-1|+|2-1|=11 從上面五個分佈曲度中，SK3與SK4的值最小，所以，取第3位與第4位為桶址： H(98123)=12 H(98089)=08 H(98563)=56 H(99073)=07 H(99429)=42

48 9-6.2 解決溢位的方法 (overflow handling)
一般常見的解決溢位的方法有下列幾種： 1. 線性探測法 ( linear probing ) 2. 鏈結串列 ( chaining ) 3. 平方探測 ( quadratic probing ) 4. 再雜湊 ( rehashing )

49 1. 線性探測法 ( linear probing )
【作法】是指將雜湊位址視為環狀的空間，當溢位發生時，以線性方式找尋一個空的儲存位址將資料存入。雖然線性探測法使用容易，但會產生「主要群集」問題，長時間的執行會增加平均的搜尋時間。如下圖所示：

50 2. 鏈結串列 ( chaining ) 【作法】將碰撞的Data放到溢位資料區(Overflow Data Area)，
並用指標連接。如下圖所示：

51 3. 平方探測 ( quadratic probing )
【作法】 當 f(x) 的位址發生溢位時，並非每次以遞增1的線性方式，而是每次加上一個常數平方的跳躍方式，亦即下一次是探測 ( f(x) + i2 ) mod b 或 ( f(x) - i2 ) mod b 的來找位址，而其中的i是代表第i次碰撞，並且1<= i <= ( b-1 ) / 2 ，b是質數。 【特性】此法是改善線性探測的缺失，避免相近的鍵值聚在一起。

52 假設有一串數列15,29,52,80，並設b=13，其雜湊函數為：H(X)=X mod b， 請利用平方探測法來解決溢位的問題。 【解答】
【範例】 假設有一串數列15,29,52,80，並設b=13，其雜湊函數為：H(X)=X mod b， 請利用平方探測法來解決溢位的問題。 【解答】 H(15)=15 mod 13=2 H(29)=29 mod 13=3 H(52)=52 mod 13=0 H(80)=80 mod 13=2 產生溢位(第1次碰撞) 進行溢位處理：( H(x) + i2 ) mod b 第1次處理：(2+12) mod 13=3 又產生溢位(第2次碰撞) 第2次處理：(2+22) mod 13=6 通過 X H(X) 位址 資料 15 29 52 80 X MOD 13 1 2 3 4 5 6 7 8 9 80第1次碰撞 80第2次碰撞

53 4. 再雜湊 ( rehashing ) 【作法】 乃是先設計好一套的雜湊函數H1，H2，H3，…，Hn，當溢位發生
【範例】 假設有一串數列15,30,52,80，並設b=13 ，並且利用以下數組「再 雜湊函數」來進行處理： 第1組雜湊函數：H1(X)=(X+2) mod b 第2組雜湊函數：H2(X)=(X+4) mod b 第3組雜湊函數：H3(X)=(X+6) mod b …… 第n組雜湊函數：Hn(X)=(X+2n) mod b 請利用再雜湊法來處理溢位的問題。

54 (4) H(80)=80 mod 13=2 產生溢位(第1次碰撞) 進行溢位處理：
【解答】 (1) H(15)=15 mod 13=2 (2) H(30)=30 mod 13=4 (3) H(52)=52 mod 13=0 (4) H(80)=80 mod 13=2 產生溢位(第1次碰撞) 進行溢位處理： 第1次處理：使用第1組雜湊函數：H1(X)=(X+2) mod b H1(80)=(80+2) mod 13=4又產生溢位(第2次碰撞) 第2次處理：使用第2組雜湊函數：H2(X)=(X+4) mod b H1(80)=(80+4) mod 13=6 通過 X H(X) 位址 資料 15 30 52 80 X MOD 13 1 2 3 4 5 6 7 8 9 80第1次碰撞 80第2次碰撞