資料結構與演算法 課程教學投影片.

Presentation on theme: "資料結構與演算法 課程教學投影片."— Presentation transcript:

1 資料結構與演算法 課程教學投影片

2 第五章–搜尋演算法 本章各段大綱 5-1 搜尋演算法概觀 5-2 線性搜尋法 5-3 二元搜尋法 5-4 插補搜尋法

3 5-1 搜尋演算法概觀 搜尋(search)是指在資料序列中找尋符合特定條件的資料 篩選功能只是搜尋方法的延伸
作搜尋時，主要是以要搜尋的資料（稱為鍵值[key value]）與資料序列中的資料作比較 搜尋根據運作過程中資料的儲存方式分類 內部搜尋:如果要搜尋的資料可以全部載入記憶體中後再進行搜尋稱為「內部搜尋」 外部搜尋:如果搜尋的資料量太大，無法全部載入記憶體中，必須藉助儲存設備(例如硬碟或磁帶)的空間再進行搜尋，稱為「外部搜尋」

4 5-1 搜尋演算法概觀 分類名稱 方法 線性搜尋法(Linear Search) 資料不用先排序，依指定次序逐一比較。
二元搜尋法(Binary Search) 資料一定要先排序好，利用二分法方法，每次搜尋資料範圍的中間位置比較，且調整要搜尋的資料範圍。 插補搜尋法(Interpolation Search) 資料一定要先排序好，利用內插法，每次找到更適合的位置比較，且調整要搜尋的資料範圍。插補搜尋法是改進二元搜尋法每次找中間點的缺點，可更快速完成搜尋。 雜湊搜尋法 (Hasing Search) 先將原資料利用雜湊函數建立雜湊表，將要搜尋的資料用同樣雜湊函數運算出位址值，比較此位址的值是否為要搜尋的資料(進一步還需處理碰撞和溢位問題)。 費氏搜尋法(Fibonacci Search) 利用費氏搜尋二元樹的特性，依樹的走訪順序來搜尋資料。

5 5-1 搜尋演算法概觀 搜尋法 平均時間 線性搜尋法 O(n) 二元搜尋法 O(log n) 插補搜尋法 雜湊搜尋法 O(1)
費伯那西搜尋法

6 5-2 線性搜尋法 線性搜尋法(Linear Search，或稱循序搜尋法)是最簡單的搜尋方法 想法: 最佳時間是O(1)
利用線性掃瞄方式（一個資料以一定的順序接著一個資料的方式）掃瞄一定範圍的資料，逐一比較。 如果要搜尋的資料與比較資料di相同時，則搜尋程序結束，否則取下一個di+1值，繼續比較。 最佳時間是O(1) 平均時間是O(n) 最差時間是O(n)

7 5-2 線性搜尋法-操作步驟

8 5-2 線性搜尋法-演算法 01 02 03 04 05 06 07 08 09 10 11 12 /* 演算法名稱：線性搜尋法 */
/* 輸入：整數陣列資料,要搜尋的鍵值 */ /* 輸出：整數陣列資料中搜尋鍵值的位置 */ int linear_search(int A[],int n,int key) { int i=0; while (i<=n-1) if (A[i]==key) return i; /* 搜尋成功 */ else i++; return -1; /* 搜尋失敗 */ }

9 5-2 線性搜尋法-演算法 複雜度 最佳狀況: 一次就找到, 複雜度 O(1) 最差狀況: 找遍所有資料, 比較n 次, 複雜度 O(n)
範例:5_2.cpp 資料存於A陣列，尋找的資料 key=77 A[20]={1,21,0,47,60,15,84,65,77,88,99,93,8,17,36,5,24,63,72,20}

10 5-3 二元搜尋法 二元搜尋法要搜尋的資料必須先排序過 想法:
假設有n筆資料以陣列A存放，且資料已由小到大排序好了，要搜尋資料的範圍其下界註標是low，上界註標是upper，key是我們要找的資料，可以先由資料的中間位置mid開始搜尋。 key和A[mid]比較有三種情況： 如果key=A[mid]，則搜尋成功，傳回mid。 如果key>A[mid]，代表有可能找到的資料位於mid+1和upper之間。 如果key<A[mid]，代表有可能找到的資料位於low和mid-1之間。 如果不是上述(a)的情況，只要調整要搜尋資料的範圍，即情況(b)的low=mid+1，upper不變；情況(c)的upper=mid-1，low不變。如果upper<low時，代表資料已搜尋完畢，且搜尋失敗；否則再計算出mid位置，再回到步驟2繼續搜尋。

11 5-3 二元搜尋法 x key<x key>x x x
mid n-1 x key<x key>x (課本有錯) mid n-1 mid n-1 x x 此段才有可能 此段才有可能 平均時間是O(log n) ,最佳時間是O(1),最差時間是O(log n) 1024筆資料只要比10次即可決定是否搜尋成功 n=1024=210,log2 n = log2 210 = 10

12 5-3 二元搜尋法-操作步驟

13 5-3 二元搜尋法 -演算法及程式 假設陣列A已存放由小到大的資料。資料量n筆，則起始upper=n-1，low=0，mid=(low+upper)/2=n/2，要搜尋的資料為key。 key和A[mid]比較有三種狀況: 如果key=A[mid] ，則搜尋成功，傳回mid。 如果key>A[mid] ，low=mid+1。 如果key<A[mid] ，upper=mid-1。 如果low<upper，則回步驟2繼續；否則搜尋失敗。 步驟2及3可以設計一個不定迴圈while來檢查。

14 5-3 二元搜尋法-演算法 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 /* 演算法名稱：二元搜尋法 */ /* 輸入：整數陣列資料,要搜尋的鍵值 */ /* 輸出：整數陣列資料中搜尋鍵值的位置 */ int binary_search(int *A,int key,int low,int upper) { int mid=0; while(low<upper) mid=(int)((low+upper)/2); if(key==A[mid]) return mid; /* 搜尋成功 */ else if(key>A[mid]) low=mid+1; else upper=mid-1; } return -1; /* 搜尋失敗 */

15 5-3 二元搜尋法- 複雜度 n筆資料的搜尋時間 最佳狀況: 一次成功，複雜度O(1)
最差狀況: While迴圈皆執行過，直至最後一次，共需O(log n) ，推演如下： 第1次: n=1024時，n/2=512=29 第2次: n=512時，n/2=256=28 ... 第9次: n=4時，n/2=2=21 第10次: n=2時，n/2=1=20 所以當n=2k時，最多要搜尋k次，k=log n 範例 5-3.cpp

16 5-4 插補搜尋法 類似二分搜尋法 將已排序好的資料以內插法找出更合適的搜尋範圍 改進二分搜尋法的另一種搜尋方法 複雜度
最佳時間是O(1) 平均時間是O(log n) 最差時間是O(log n) 適用情況: 資料分佈均勻時，搜尋速度極快

17 5-4 插補搜尋法-理論 (A數列) 10，15，21，26，31，37，43，49，54
(B數列) 10，11，13，25，31，32，34，36，38，40 (A)數列兩兩差距為5或6，即很接近，近似均勻分佈 (B)數列兩差距有1，2，6，12，資料集中在31~40範圍，為不均勻分佈。 均勻分佈的資料有一個等差的特性，即用除法的比率來看 以數列(A)為例: 　(d2-d1)≈(d3-d2) ≈ (d4-d3) ≈………≈(d9-d8)=k 　則d9-d1≈(d9-d8)+(d8-d7)+………+(d2-d1) ≈(9-1)*(d2-d1) 　所以d2-d1≈(d9-d1)/(9-1) (1) d1 d2 d3 . d8 d9

18 5-4 插補搜尋法-理論 所以di-d1≈(di-di-1)+(di-1-di-2)+………+(d2-d1)=(x-1)(d2-d1)
di-d1=(d9-d1)/(9-1)*(i-1)或者 di=d1+(d9-d1)/(9-1)*(i-1) 其中(di-d1)/(d9-d1) ≈(i-1)/(9-1)即為內差公式，假如符合內插特性的資料，可以由起始點(如d1)和終止點(如d9)來求得其中di的值，且約為下列公式 di≈d1+(dn-d1)/(n-1)*(i-1) (3) d1 d2 d3 . di d8 d9

19 5-4 插補搜尋法-理論 di≈d1+(dn-d1)/(n-1)*(i-1)---------(3)
插補搜尋法即假設di是我們要搜尋的值，約符合上述式子(3)，而反過來i的值以式子(3)調整如下： i=1+(di-d1)/(dn-d1)*(n-1) (4) 如果不是以d1和dn作內插法，而是dm和dn作內插法，同樣可得： i=m+(di-dm)/(dn-dm)*(n-m) (5) 設定搜尋控制變數為upper，low和mid分別代表搜尋範圍的上界註標，下界註標和要搜尋的註標，x表示要搜尋的值。 例如下述A陣列的值，low=0，upper=8，代入上式， 得第一次要搜尋的位置mid=0+[(21-10)*(8-0)]/(54-10)=88/44=2 A[2]即等於21，一次即搜尋成功，但注意這是資料分佈的很均勻，才會有這麼好的效果，但只要資料有點均勻，也是可得到比二分搜尋法好的效果。 d1 d2 dn . di dm d9

20 5-4 插補搜尋法-理論 由步驟推演得知 mid=low+(x-A[low])*(upper-low)/(A[upper]-A[low])
其中upper，lower是目前要搜尋範圍的上界和下界註標，A[low]，A[upper]是資料值，x是欲搜尋的資料，mid則是建議你搜尋的位置。 決定mid位置時，用A[mid]和x比較，有下列三種情況： A[mid]=x，搜尋成功 A[mid]>x：表示欲搜尋的x必定在mid位置之前，所以調整上界範圍為mid-1，即upper=mid-1。 A[mid]<x：表示欲搜尋的x必定在mid位置之後，所以調整下界範圍為mid＋1，即low=mid+1。

21 5-4 插補搜尋法-演算法 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 /* 演算法名稱：插補搜尋演算法 */ /* 輸入：整數陣列資料,要搜尋的鍵值 */ /* 輸出：整數陣列資料中搜尋鍵值的位置 */ int search(int x) { int low=o,upper=max-1,mid; /*max是陣列宣稱的維數*/ mid=low+(x=A[low])*(upper-low)/(A[upper]-A[low]); if(mid<low) mid=low; in(mid>upper) mid=upper; while(low<=upper) if(x=A[mid]) return 1; /*搜尋成功*/ else if(x<A[mid]) upper=mid-1; else if(x>A[mid]) low=mid+1; if(low<upper) mid=low+(x-A[low])*(upper-low)/(A[upper]-A[low]) if(mid>upper) } return 0; /*搜尋失敗*/

22 5-4 插補搜尋法-範例 範例: 5_4.cpp 利用差補搜尋法，對下列資料搜尋50 low=0,upper=9
由mid=low+(x-A[low])*(upper-low)/(A[upper]-A[low]) 得知mid=0+(50-1)*(9-0)/(100-1)=40*9/99 ≒ 4 所以mid=4,A[4]=38/50 所以low=mid+1=4+1=5 low=5,upper=9 所以mid=5+(50-44)*(9-5)/(100-44)=5+6*4/54 ≒ 5 比較A[5]=44<50 所以low=mid+1=6 (3) low=6,upper=9 所以mid=6+(50-46)*(9-6)/(100-46) ≒6 比較A[6]=46<50 所以low=mid+1=6+1=7 (7) low=7,upper=9 所以mid=7+(50-50)*(9-7)/(100-50) ≒7 比較A[7]=50, 所以搜尋成功, 序列A中,A[7]=50 1 2 3 4 5 6 7 8 9 15 27 38 44 46 50 58 100 範例: 5_4.cpp