Search

Search

搜尋。在資料結構當中,找出一個東西的位置。常與Search相提並論的則是Sort:在資料結構當中,把所有東西排好順序,放在正確位置。另外還有Select:在資料結構當中,選出一個符合特徵條件的東西。

資料結構千變萬化,各有其獨特的Search、Sort、Select演算法。在陣列中,便有Binary Search、Bubble Sort、Quick Select這些演算法;在圖論中,則有Depth-first Search這樣的演算法。甚至也有專為Search、Sort、Select而設計的資料結構,如各種Priority Queue、各種Search Tree、Hash Table、……等等。

Sequential Search

【待補文字】

Binary Search

相信各位都耳熟能詳。細節的部分可以去翻閱演算法的書籍,或在網路上搜尋「Binary Search」或中文「二元搜尋法」,都可以找到詳細的資料。

Binary Search的基本原理也是D&C。若是資料是以陣列呈現──Binary Search是將一個將排序好的陣列,分為大的一邊和小的一邊,再看看我們要找的元素會在哪一邊。如此下去直到找到為止。分割的時候,也是採用對半分,想當然時間複雜度是O(logn),以2為底的logn。

這裡提供個程式碼。它會回傳陣列中等於pivot的值的index,如果陣列中沒有等於pivot的值,就會回傳比pivot稍大一點的值的index。

我想大家最好自己重新寫一個,並驗證它在任何情形下,結果都會是正確無誤的,而不會有超出陣列範圍的結果。另外也請看看這篇文章:Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

上面這支程式亦可改用遞迴寫出來,不妨試試。

延伸閱讀:Binary Search的功用

Binary Search的功用,是在一個排序過的數列(即是遞增、遞減數列)當中,找出某個數字的索引值(index)。以數學的角度來看,Binary Search是在一個遞增(或遞減)的函數y = f(x)中,當我們知道y值時,用來快速的計算出x。

資料往往都是排序整齊的,也因此,Binary Search常被用來加速程式。一旦看到數據資料有排序、遞增遞減、成正比反比的時候,便要想到Binary Search。

還有一種常見的應用是:現在有一個遞增函數y = f(x),當x小於等於c時,f(x)會滿足某種條件;當x大於c時,f(x)就不會滿足某種條件──現在要把c求出來,便可以用Binary Search。

很多問題其實都隱含著上述這種性質,只是不容易發現。去發現問題隱含了這種性質,並去寫程式解決問題,這便是程式設計深奧且有趣之處。

這裡枚舉一些可以練習Binary Search的題目。你可以體驗一下D&C的感覺。

UVa 10611 10077

延伸閱讀:Search in Sorted 2D Matrix

一個排序過的陣列可以用Binary Search來搜尋數值,那麼一個排序過的二維矩陣呢?當一個二維矩陣裡的元素經過排序,任一位置往右、往下都呈現嚴格遞增時(嚴格遞減也行),此時有個很巧妙的搜尋方式,時間複雜度為O(X+Y),X與Y分別為矩陣的長與寬。

首先在腦中將矩陣的元素切割為大於n的一邊(右下角)與不大於n的一邊(左下角)。現在我們所要作的,便是遊走於大與小的邊緣來尋找n!從矩陣的右上角開始,嘗試走到左下角,若走到了大於n的一邊,就立即往不大於n的另一邊移動,反之亦同。

各位可以想想當找到目標元素時,應該往左還是往下走好?當矩陣元素是非嚴格遞增的時候會產生什麼問題?

Ternary Search

【待補文字】

Interpolation Search

【待補文字】