一般來說 搜尋 Search 與 排序 Sort 這兩個東西是常常會被放在一起討論, 如果還沒看過 Jason寫的【演算法】排序演算法 Sorting Algorithm 系列文章的,可以參考看看。 搜尋 Search:就是在資料結構中,找到一個東西的所在位置。 在不同的資料結構上有各式各樣不同的搜尋演算法,像如果是應用在圖形 ( Graph )或樹 ( Tree ) 的話,那我們最常討論的就是深度搜尋跟廣度搜尋。不過呢今天要介紹的比較簡單,是針對陣列( Array ) 做 Search。 一、線性搜尋法 Linear Search
如果今天我們想要搜尋的資料陣列是未經排序 ( Unsorted ) 的,那最簡單的做法就是採用線性搜尋法。
線性搜尋法 ( Linear Search ),又稱「循序搜尋法 Sequential Search」,即依序一個Element 一個 Element 查看,無一遺漏。 演算法的時間複雜度為:O(N) 。
Linear Search
二、二元搜尋法 Binary Search
如果今天要搜尋的資料是已經排序過的,那我們就可以使用二元搜尋法 ( Binary Search ) 來進行搜尋。
二元搜尋法也可稱作「 二分搜尋法」,概念就像我們國小國中玩猜數字的時候一樣,1~100 你不知道真正的答案是多少,你就會從1~100 砍半去猜50,讓出題者告訴你答案大於50 或者是小於50,進而縮減範圍希望能比較快猜出正確答案。 而所謂的二元搜尋法正是這樣!它會將資料分成兩部份,再將我們要找的目標數字與中間值比較,如果相等則代表找到了,小於的話就再比前半段,大於的話則再比後半段。如此反覆,不停的分段比較至找到目標所在位置或者陣列中無匹配資料為止。所以二元搜尋法又可稱作「折半搜尋法」。
Binary Search
三、內插搜尋法 Interpolation Search
內插搜尋法就是基於前面介紹到的二元搜尋法的改良版!
改良的想法是依照資料位置分佈,運用公式預測資料所在位置,再以二分法方式逼近。 而預估的方法、公式,我們會假定排序後資料的分佈是會呈現一個線性的分佈,類似這個樣子:
如果資料真的呈現這個樣子那就簡單了!
這時候你只要用高中的數學(直線方程式)就可以用來表示這樣的資料分佈,進而你就可以用來加以預估某一筆資料可能在哪個位置上。 一般而言,資料量如果越大,數值的分佈就會越來越均勻,越容易呈現線性。所以在資料量大的時候,內插搜尋法的效率通常會優於二元搜尋法,當然會有某些 Special Case 可能不是這樣,但也不需要過度的去探討那個。
實作上,我們只要使用斜率的觀點來求解就好了。
對應上圖,其中 y 為我們要找的 target 的數值,x 為我們需要function 回傳給我的 y 在陣列中的 index 值。 至於 ( x1, y1 )、( x2, y2 ) 這兩個點,其實就是原本二元搜尋裡面的 high 跟 low 兩點。
Interpolation Search
四、二元樹搜尋法 Binary Tree Search
其實所謂的二元樹搜尋法就是利用在資料結構(Data Structure)裡面講的二元搜尋樹(Binary Search Tree)。
看完前面你們大概也感受的出來,線性搜尋法的效率其實不太好,算是蠻笨的一種方法。 但是如果原始資料沒有經過排序,你也不能直接使用二元搜尋法,這時候你可能就要先把資料作排序,如果資料量很大的時候,可能單單作排序這件事情的時間雜度就很高了。 然而這個時候就可以考慮使用在資料結構裡面學到的二元搜尋樹的方法! 把陣列資料建成二元搜尋樹:
一開始資料在建的時候就把比自己小的資料往左子樹送,比自己大的往右子樹送,這樣一來事後要查詢資料也會變的相當的便利,不過缺點是每個 Data Node 都要多記錄兩個指標,所需要的記憶空間會比較大。
Binary Tree Search
上面是做 Search 部分的 code,如果資料結構不太熟,不知道怎麼建node、做資料加入、插入、刪除的,那.. 你可能要自己先去找一些資料結構的東西來看比較好。 Jason 是不知道之後會不會有空來寫這部分的解說啦... 資料結構跟演算法可以說是 Computer Sciences 裡最重要的基礎,凡是對寫程式有興趣、想把程式寫好的,都蠻建議好好研究這兩門學科。 五、雜湊搜尋法 Hashing Search
最後這個部分,Jason 想說大概講個概念就好。
因為如果不懂 雜湊Hash 的話大概也很難理解這個搜尋演算法在做什麼。 這東西的作法跟前面所提到那些都不樣的點是,它在存取資料時,並不是依照資料的順序做存取,而是利用資料中某欄位的值,把它代入到事先設計好的雜湊函數,用來計算資料存放之位置,這種方式稱做雜湊法(Hashing)。 這樣做的好處是:
但是有好處,自然也會有一些壞處啦~ 就像 Jason 之前講過的,在 CS 領域很多演算法的設計都是 trade off 的。 缺點的話:
0 評論
發表回覆。 |
Jason Chen人不光是生來就擁有一切,而是靠他從學習中得到的一切來造就自己。- 歌德 文章分類
全部
封存檔
九月 2023
|