From Wikipedia, the free encyclopedia
搜尋演算法(粵音:sau2 cam4 jin2 syu3 faat3;英文:search algorithm),又或者叫檢索演算法,係指用嚟由數據結構當中搵出一件目標數據嘅演算法。廿一世紀嘅電腦科學界有多種搜尋演算法可以用,而每種都有優缺點[1]。
窮舉搜尋(brute-force)係最原始嗰種搜尋演算法,指將手上嘅數據(事先以某啲方式排好咗)逐個逐個耖,一路耖到搵到想要嗰個為止。例如手上有一列以隨機次序排嘅數字,用家想要由呢個數列當中最大嗰個出嚟,用窮舉搜尋嘅話,睇嗰個人就要睇嗮個數列當中嘅每個數字,再俾出最大嗰個出嚟;呢段簡單嘅演算法用粵文寫出嚟嘅話會係[2]:
上述呢個演算法用比較形式些少嘅虛擬碼寫出嚟嘅話會係噉:
// Input: A list of numbers L.
// Output: The largest number in the list L.
if L.size = 0 return null;
largest ← L[0];
for each item in L, do
if item > largest, then
largest ← item;
return largest;
// 當中 "←" 代表指定敘述-「A ← B」即係將 A 嘅數值設做 B;
// 而 "return X" 會終止個演算法,並且將 X 嘅數值攞嚟做輸出。
廿一世紀嘅研究者一般都會嫌呢個演算法唔夠好,原因係呢個演算法喺最壞情況(worst-case)嗰陣要睇嗮成個列先至搞得掂,所以又有人諗咗第啲演算法出嚟做呢樣工作-而呢啲新演算法好多時都曉淨係睇個數字列嘅一小部份就經已搵得出想要嗰個數字[1]。
對分檢索(binary search)係用嚟由一個預先排好咗次序(睇排序演算法)嘅數列嗰度搵某一個特定數字出嚟嘅演算法。對分檢索嘅做法係首先將行資料拆做兩橛,再睇吓中間嗰個數係咪等如要搵嗰個數(目標),假如個數列係預先由細到大排好咗嘅話,噉就意味一樣嘢:如果數列中間嗰個數大過個目標,噉個目標實係喺中間個數前面,而如果數列中間嗰個數細過個目標,噉個目標實係喺中間個數後面,跟手段演算法就可以再重複呢個程序,將個搜索範圍縮細,最後搵到個目標嘅數字(假如個目標真係存在喺嗰行數列入面嘅話)。好似係以下呢段虛擬碼噉[3][4]:
function binary_search(A, n, T):
L := 0 // 設個數做「左邊界」
R := n − 1 // 設個數做「右邊界」
while L <= R:
m := floor((L + R) / 2) // 將由 L 至 R 嗰段嘢砍兩橛,m 設做中間位
if A[m] < T: // 如果第 m 個數細過目標(T)嘅話,即係話個目標應該喺第 m 個數後面。
L := m + 1
else if A[m] > T: // 如果第 m 個數細過目標(T)嘅話,即係話個目標應該喺第 m 個數前面。
R := m - 1
else:
return m // 如果第 m 個數等如目標嘅話,就將嗰個數做輸出。
return unsuccessful
對分檢索平均會快過「吓吓都將數列入面嘅數逐個逐個睇一次」嘅窮舉搜尋:喺最壞情況下,想搵嗰個數會係個數列嘅第一個或者最尾嗰個,而喺呢個情況下,用對分檢索嚟做搜尋要做 咁多次比較(當中 係「個數列入面有幾多個數字」),而「吓吓將數列入面逐個逐個睇一次」喺最壞情況之下就要做 次比較, 數值永遠細過 [註 1]。「由一個數列當中搵一個特定數字出嚟」係電腦好常要做嘅基本作業,如果(例如)喺一個程式當中部電腦要做呢個作業 100 次嘅話,噉一個用對分檢索嘅程式基本上實會快一截,所以編程員多數會比較鍾意用對分檢索[3]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.