繁體中文

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

國中電腦科學對已排序的唯一偶數整數陣列進行精確搜尋，索引從零開始

使用通行證解鎖此實驗

通行證可解鎖網站上的所有模擬，包括課堂展示模式。下方的教學筆記仍免費開放給所有人。

查看通行證我已經有通行證

一次性付款，無需訂閱。

關於此實驗

並排使用線性搜尋和二分搜尋查找相同的目標。每一步中，每種尚未結束的演算法各進行一次比較。二分搜尋檢查剩餘排序區間的中間位置；線性搜尋則每次向前移動一個位置。選擇奇數作為目標，可以看到兩種演算法都在找不到相符項目的情況下結束。

學習目標

  • 追蹤二分搜尋中的候選區間和中間位置
  • 比較線性搜尋和二分搜尋的比較次數
  • 說明二分搜尋為何需要排序資料，以及如何處理不存在的目標

使用方法

  1. 1在預設陣列中搜尋32，每次進行一次比較。
  2. 2注意二分搜尋何時結束，然後繼續執行，直到線性搜尋結束。
  3. 3選擇一個奇數目標，例如31。觀察二分搜尋如何得到空區間。
  4. 4變更陣列長度並搜尋最後一個值。比較最壞情況下的上界。

模型

二分搜尋中包含低索引和高索引的中間位置
二分搜尋值比較次數的上界
此處所示線性搜尋在最壞情況下的比較次數

假設

  • 陣列包含依遞增順序排列且互不重複的偶數整數 2、4、…、2n。索引從 0 開始。
  • 一次值比較是與目標值進行的一次三向比較。索引運算和迴圈條件檢查不計入比較次數。
  • 若目標值不存在，線性搜尋會掃描整個陣列，不會利用陣列已排序這一點進行提前停止最佳化。
  • 一列會保持在其搜尋已完成的狀態，同時另一種搜尋繼續進行。目前的候選區間會在套用目前的探測結果之前顯示。

在課堂上試試這個實驗

  1. Q1為什麼二分搜尋只需比較一次，就可以排除剩餘位置的一半？
  2. Q2在一個包含 32 個值的陣列中，用每種方法尋找最後一個值分別需要進行幾次比較？
  3. Q3如果將相同的中點規則套用至未排序的陣列，會出什麼問題？

常見問題

為什麼二分搜尋無法找到奇數目標值？

陣列中的每個元素都是偶數。奇數目標值不可能相符，因此候選區間最終會變空，演算法會回報找不到。

為什麼其中一列不再移動了？

該搜尋已完成。繼續逐步執行會讓另一種演算法繼續執行，以便比較兩者的總比較成本。