第 十一 章 搜尋(Search) 課程名稱：資料結構 授課老師：________ 2019/5/22.

Presentation on theme: "第 十一 章 搜尋(Search) 課程名稱：資料結構 授課老師：________ 2019/5/22."— Presentation transcript:

1 第 十一 章 搜尋(Search) 課程名稱：資料結構 授課老師：________ 2019/5/22

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

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

4 11-1 搜尋(Search) 所謂搜尋(Search)就是在一群資料中找尋所要的特定資料。當資料量很龐大時，如何快速搜尋到資料是本章所要探討的重點。 一般電腦檔案都是記錄的集合，每一筆記錄包含許多欄位，其中必須至少有一個欄位可當作主鍵值（key），從資料檔案中找出滿足主鍵值的記錄之動作稱之為搜尋（search）。例如，我們在電話簿中找某人的電話，那麼這個人的姓名就成為在電話簿中搜尋電話資料的主鍵值。 2019/5/22

5 欲找尋的資料或檔案較小，可以直接全部載入記憶體中來進行搜尋的 動作。 2.外部搜尋：
若依資料量大小來區分，搜尋可分為： 1.內部搜尋： 欲找尋的資料或檔案較小，可以直接全部載入記憶體中來進行搜尋的 動作。 2.外部搜尋： 若要找尋的資料數目很大，無法一次將全部內容置於主記憶體內，而 需使用到外部的輔助記憶體來分批處理。 2019/5/22

6 指在搜尋過程中，資料不會有任何異動時，亦即增加、刪除或更新等 行為。 例如：紙本的字典、電話簿
除了上述的分類方式之外，我們還能以搜尋過程中被搜尋的表格或資料是否異動，區分為靜態搜尋(Static Search)及動態搜尋(Dynamic Search)。 1.靜態搜尋(Static Search) ： 指在搜尋過程中，資料不會有任何異動時，亦即增加、刪除或更新等 行為。 例如：紙本的字典、電話簿 2.動態搜尋(Dynamic Search) ： 在搜尋過程中，資料會經常異動時，亦即增加、刪除或更新等行為。 例如：日常交易資料、電腦字典 2019/5/22

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

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

9 【時間複雜度】 如果資料沒有重覆，找到資料就可中止搜尋的話，在最差狀況是未找到資料，需作n次比較，時間複雜度為O(n)。
2019/5/22

10 【演算法】 2019/5/22

11 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

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

13 【時間複雜度】 因為每次的搜尋都會比上一次少一半的範圍，最多只需要比較[log2N]+1或[log2(N+1)]，時間複雜度為O(Log2N)。 1. 平均時間是O(log2n) ,最佳時間是O(1),最差時間是O(log2n) 筆資料只要比10次即可決定是否搜尋成功 n=1024=210 log2 n = log2 210 = 10 2019/5/22

14 【概念圖】 每一次皆與Search範圍的中間記錄進行比對 2019/5/22

15 【演算法】 void binsearch(A[], key , low, high) { int mid; if(low<=high)
switch compare(key,A[mid]) Case "=": return mid; //找到 Case "<": return binsearch(A, key, low, mid-1) ; //要找的資料在左半部 Case ">": return binsearch(A, key, mid+1, high) ; //要找的資料在右半部 } Reture -1; //搜尋失敗，傳回-1 2019/5/22

16 【作法】 在二分搜尋法中，從數列的「中間」開始搜尋，如果這個數小於我們所搜尋的數，由於數列已排序，則該數左邊的數一定都小於要搜尋的對象，所以無需浪費時間在左邊的數列；如果數列中間的數大於所搜尋的對象，則右邊的數無需再搜尋，直接搜尋左邊的數列。 2019/5/22

17 步驟 設L(Low)表示第一項資料(最小)，H(High)表示最後一項資料(最大)。 步驟 M(Middle)表示中間項數＝
其步驟如下： 步驟 將所有資料由小至大排序。 步驟 設L(Low)表示第一項資料(最小)，H(High)表示最後一項資料(最大)。 步驟 M(Middle)表示中間項數＝ 步驟 將「目的資料」和「中間項的資料」做比較。 當目的資料＞中間項資料，則L＝M＋1。 當目的資料＜中間項資料，則H＝M－1。 當目的資料＝中間項資料，則表示已經找到。 步驟 重定M，重覆步驟和，直到找到或所有資料均找過為止。 2019/5/22

18 【實例】 原始資料：8,1,99,76,88,45,15,33,24 2019/5/22

19 2019/5/22

20 2019/5/22

21 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

22 比較循序搜尋法與二分搜尋法 2019/5/22

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

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

25 2019/5/22

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

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

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

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

30 而使用內插法是假設資料平均分佈在陣列中，而每一筆資料的差距是相當接近或有一定的距離比例。其內插法的公式為：
Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low ) 如果欲搜尋的資料分佈平均的話，可以使用內插（Interpolation）搜尋法來進行搜尋，在搜尋的對象大於500時，內插搜尋法會比二分搜尋法來的快速。 2019/5/22

31 (A)數列兩兩差距為5或6，即很接近，近似均勻分佈 (B)數列兩兩差距有1，2，6，12，資料集中在30~40範圍，為不均勻 分佈。
【舉例】 (A數列) 9，14，20，25，30，36，42，48，53 (B數列) 9，10，12，24，30，31，33，35，37，40 【分析】 (A)數列兩兩差距為5或6，即很接近，近似均勻分佈 (B)數列兩兩差距有1，2，6，12，資料集中在30~40範圍，為不均勻 分佈。 2019/5/22

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

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

34 【內插搜尋法的步驟】 key是要尋找的鍵，data[high]、data[low]是剩餘待尋找記錄中的最大值及最小值，對資料筆數為n，內插搜尋法的步驟如下： 步驟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 2019/5/22

35 【範例】利用內插搜尋法，對下列資料搜尋50 2019/5/22

36 2019/5/22

37 11-6 雜湊搜尋法(Hashing Search)
【定義】 將資料按照某種特定的法則，將鍵值 ( key value) 轉換成資料的儲存位址。如圖11-1所示。 2019/5/22

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

39 【缺點】 (1)浪費空間(因為有溢位區)，儲存空間的利用率比循序檔差。
(2)有碰撞問題(Collision)，當資料檔記錄到一定量時，會嚴重影響處理 速度及存 取速度。 (3)程式設計比較複雜。 (4)大量資料無效率。 (5)不適合循序型的媒體。如磁帶。 2019/5/22

40 11-6.1雜湊函數 ( hashing function )
尚未介紹雜湊函數之前，先介紹有關雜湊函數的相關名詞： 1.桶 ( bucket ) 雜湊表中儲存資料的位置，每個位置被給定一個唯一的位址，稱之為 bucket address 。 2.槽 ( slot ) 每一個桶可能有好幾個儲存區，此儲存區便稱之為槽 ( slot ) 。每一個槽 可以容納一個記錄。 3.碰撞 ( collision ) 當兩個不同的識別字經過雜湊函數運算後，落在相同的 bucket address ， 稱之為碰撞。 4.溢位 ( overflow ) 如果一個識別字經過雜湊函數運算後，所對應的 bucket 已經滿了，就稱 之為溢位。 2019/5/22

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

42 1. 中間平方法 ( mid - square ) 此法是將鍵值平方後，取出中間某些位元來當作資料儲存的位址。例如我們可以利用中間平方法將英文字的「ABC」轉換為雜湊表中的位置。如圖11-2所示。 2019/5/22

43 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

44 2. 折疊法 ( folding ) 此法是將鍵值分為數段，除了最後一段外，其餘各段皆須等長，然後將
每一段相加，即可得到其所對應的位址。在相加的時候，有兩種方式： 位移折疊 ( shift folding ) (2) 邊界折疊 ( folding at the boundaries ) 2019/5/22

45 (1) 位移折疊 ( shift folding )
將各段資料直接相加。 【範例】 假設有一個鍵值為 ，其儲存位址為何？ 【解答】 假設將其切割成 5 段，如下所示： 2019/5/22

46 (2) 邊界折疊 ( folding at the boundaries )
將奇數位段或偶數位段反轉後相加。 【範例】 假設有一個鍵值為 ，其儲存位址為何？ 【解答】 假設將其切割成 5 段，如下所示： 2019/5/22

47 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

48 3. 除法 ( Division ) 此法利用Mod運算，將識別字 X 除以某一個數值 M ，取其餘數當做 X 的位址。這個位址介於 0 ~ M-1 之間。而在使用除法時，一般建議利用質數會有較佳的效果。 即 H( X ) = X mod M 2019/5/22

49 2019/5/22

50 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

51 4. 數字分析法 ( digit analysis )
數字分析法有二種： (1)目視數字分析法： 利用目視法，將Key分佈不平均的數字刪除，其餘保留為Hash位址。 (2)統計數字分析法： 利用統計方法分析鍵值各位數的分析情形，求出Hash位址。 2019/5/22

52 (1)目視數字分析法： 【範例】假設有5位同學，其學號共有五位數(N1,N2,N3,N4,N5)，分別為： S1_No：98123
將以上五位同學的學號列表如下： 2019/5/22

53 如果我們使用「目視數字分析法」來觀察上面表格，可以得知： N1桶址中的數字：只有9 N2桶址中的數字：只有8與9
N3、N4及N5桶址中的數字分佈比較平均(被取用) 雖然我們可以選出N3、N4及N5中的2個桶址來使用，但是利用「目視數字分析法」無法保證是最佳的選擇，並且沒有科學，因此，我們可以利用「統計數字分析法」。 2019/5/22

54 (2)統計數字分析法： 【範例】假設有5位同學，其學號共有五位數(N1,N2,N3,N4,N5)，分別為： S1_No：98123
將以上五位同學的學號列表如下： 2019/5/22

55 (2)統計數字分析法： 2019/5/22

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

57 1. 線性探測法 ( linear probing )
又稱為線性開放定址 ( linear open addressing )。其做法是將雜湊位址視為環狀的空間，當溢位發生時，以線性方式找尋一個空的儲存位址將資料存入。雖然線性探測法使用容易，但會產生「主要群集」問題，長時間的執行會增加平均的搜尋時間。如下圖所示： 2019/5/22

58 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

59 2. 鏈結串列 ( chaining ) 將碰撞的Data放到溢位資料區(Overflow Data Area)，並用指標連接。如下圖所示：
2019/5/22

60 【老師上課動態展示】檔案在附書光碟中。 2019/5/22

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

62 2019/5/22

63 4. 再雜湊 ( rehashing ) 　乃是先設計好一套的雜湊函數H1，H2，H3，…，Hn，當溢位發生時先使用H1，若再發生溢位則使用H2……，一直到沒有溢位發生。 【範例】 假設有一串數列15,30,52,80，桶址b=13，並且再雜湊函數有以下n組可使用： 第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 請利用再雜湊法來處理溢位的問題。 2019/5/22

64 【解答】 2019/5/22