搜尋演算法

二分搜尋
類別	搜尋演算法
資料結構	陣列
最壞情況效能	O(log n)
最佳情況效能	O(1)
平均情況效能	O(log n)
最壞情況空間複雜度	O(1)

試卷 1 - ⇑ 演算法基礎 ⇑
← 逆波蘭	搜尋演算法	排序演算法 →

搜尋演算法在給定資料結構中查詢給定項。使用的演算法取決於資料的結構方式。

線性搜尋

如果你有一個未排序的列表（或陣列），那麼最簡單的搜尋演算法是線性搜尋：逐項遍歷列表，並與搜尋項進行比較。如果比較成功，則演算法已找到該項。如果所有比較都失敗，則該項不存在於陣列或列表中。

在最簡單的變體中，演算法返回一個布林值以指示成功或失敗。以下是虛擬碼

for each item in the list:
    if that item has the desired value then
        stop the search and return true
return false

可以直接翻譯成 Python

def exists(soughtItem, aList):
  """Return True if and only if soughtItem occurs in aList."""
  for item in aList:
    if item == soughtItem:
      return True
  return False

# automatic tests
assert exists(2, [2, 1, 3]) # sought item in first position
assert exists(3, [2, 1, 3]) # sought item in last position
assert not exists(3, []) # list is empty
assert not exists(0, [2, 1, 3]) # sought item doesn't exist

第二個變體返回列表中該項的位置（如果存在）。如果不存在，則演算法返回一個不可能的位置，例如 -1。以下是虛擬碼

For each position in the list:
    If the item at that position has the desired value then
        stop the search and return the position
Return -1

以下是 Python 程式碼

def index(soughtItem, aList):
  """Return the position of soughtItem in aList if it exists, otherwise return -1."""
  for position in range(len(aList)):
    if aList[position] == soughtItem:
      return position
  return -1

# automatic tests
assert position(2, [2, 1, 3]) == 0 # sought item in first position
assert position(3, [2, 1, 3]) == 2 # sought item in last position
assert position(3, []) == -1 # list is empty
assert position(0, [2, 1, 3]) == -1 # sought item doesn't exist

以下完整的 VB 程式會提示使用者輸入一個字母，並在陣列中搜索它。

dim items() = {"h","g","a","d","w","n","o","q","l","b","c"}
dim searchItem as string

console.write("What are you searching for: ")
searchItem = console.readline()

For x = 0 to 10
  If items(x) = searchItem Then
    console.writeline("Found item " & searchItem & " at position " & x)
    Exit For
  End If
Next
console.writeline(-1)

嘗試上述程式碼，搜尋字母“w”，然後搜尋字母“z”。

程式碼輸出

你要搜尋什麼：w
在位置 4 找到項 w

程式碼輸出

你要搜尋什麼：z
-1

練習：線性搜尋

考慮字串列表“Cat”、“Mouse”、“Frog”、“Lion”、“Panda”、“Llama”、“Bee”，按此順序排列。找到“Panda”需要多少次比較？

答案

5

而搜尋“Camel”需要多少次比較？

答案

需要 7 次比較才能得出該字串不在列表中的結論。

為上述程式碼製作一個跟蹤表，其中 searchItem = "d"。

答案

searchItem	x	輸出	item
searchItem	x	輸出	0	1	2	3	4	5	6	7	8	9	10
d	0		h	g	a	d	w	n	o	q	l	b	c
	1
	2
	3	在位置 3 找到項 d

對於一個包含 $n$ 個專案的列表，要檢視專案是否存在，需要進行的最大比較次數是多少？

答案

如果專案位於最後一個位置或根本不在列表中，則需要進行 $n$ 次比較。

二分搜尋

正如最後一個問題所指出的，線性搜尋可能需要與列表中專案數量一樣多的比較次數，因此在一個包含數百萬個名稱的列表（例如一個國家的選民登記冊）中搜索一個名字可能會花費很長時間。

如果你的列表按升序排列，可以使用排序演算法，那麼你可以執行二分搜尋。這涉及在每次比較時將資料分成兩半，從而更快地“縮小”到專案必須在列表中的部分（如果存在）。這會導致效能顯著提升，如側邊欄所示（大 O 表示法在單元 4 中解釋）。

讓我們在以下排序列表中搜索名稱 Miles

Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne

我們將 Miles 與中間名稱 Mohammed 進行比較

Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne

Miles 在字母順序上位於 Mohammed 之前，因此我們知道 Miles 不會位於 Mohammed 的右側。因此，我們可以“丟棄”列表的右半部分

Ali, Bernie, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

我們現在將 Miles 與剩餘列表中的中間名稱 Bernie 進行比較

Ali, Bernie, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

Miles 在字母順序上位於 Bernie 之後，因此我們可以丟棄左側

~~Ali, Bernie~~, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

最後，我們將 Miles 與此單項列表的中間名稱 Claire 進行比較

~~Ali, Bernie~~, Claire, ~~Mohammed, Peter, Simon, Yvonne~~

Miles 與 Claire 不相同，沒有更多項可比較，因此我們知道 Miles 不在列表中。

這僅使用二分搜尋進行了 3 次比較，而使用線性搜尋則需要 7 次比較。當列表很大時，效果會更好。例如，一個包含 1,000,000,000 個專案的列表僅使用二分搜尋最多隻需要進行 30 次比較！擁有排序資料非常有用。

練習：線性搜尋與二分搜尋

排序資料對於線性搜尋也很有用。修改後的線性搜尋演算法在搜尋 Miles 時如何能夠進行少於 7 次比較？

答案

修改後的線性搜尋會在 4 次比較（與 Ali、Bernie、Claire 和 Mohammed 比較）後知道 Miles 不在排序列表中，因為 Miles 應該在 Mohammed 之前出現。

對於上面顯示的包含 7 個名稱的列表，你能想到線性搜尋比二分搜尋更快的案例嗎？

答案

如果我們搜尋列表中的第一個專案 Ali，二分搜尋仍然需要 3 次比較（與 Mohammed、Bernie 和 Ali 比較），但線性搜尋只需要 1 次比較。

對於大型列表的線性搜尋，最佳情況是搜尋的專案位於第一個位置。對於大型列表的二分搜尋，最佳情況是什麼？

答案

如果搜尋的專案位於列表的中間，則二分搜尋只需要進行 1 次比較。

每次不成功的比較後，二分搜尋都會將搜尋空間減半。正在搜尋的子列表可以用兩個整數表示，它們表示子列表的起始和結束位置。Python 程式碼如下

def index(soughtItem, sortedList):
  """Return the position of soughtItem in sortedList if it exists, otherwise return -1.
  sortedList must be in ascending order."""
  # Initially, the sublist is the whole list of N items, from positions 0 to N-1
  start = 0
  end = len(sortedList) - 1
  while start <= end:                    # while the sublist is not empty
    middle = (start + end) // 2
    if soughtItem == sortedList[middle]: # the item is in the middle of the sublist
        return middle
    if soughtItem >  sortedList[middle]: # the item is in the right half
        start = middle + 1  
    if soughtItem <  sortedList[middle]: # the item is in the left half
        end = middle - 1   
  return -1                              # empty sublist, the item doesn't exist
  
# tests
assert index(3, [1, 2, 3]) == 2
assert index(1, [1, 2, 3]) == 0
assert index(1, []) == -1
assert index(0, [1, 2, 3]) == -1

單元 3 - ⇑ 演算法基礎 ⇑
← 逆波蘭	搜尋演算法	排序演算法 →