27. 以下關於二分搜尋演算法的原理和範例說明何者有誤？
(A) 平均時間複雜度 O(log n)
(B) 疊代的空間複雜度為 O(log n)
(C) 二分搜尋演算法使用常數空間，對於任何大小的輸入資料，演算法使用的空間都是一樣的
(D) 除非輸入資料數量很少，否則二分搜尋演算法比線性搜尋更快，但資料必須事先被排序

二分搜尋（Binary Search）演算法是一種高效的搜尋演算法，但它有一些特定的要求和特性。讓我們逐一分析每個選項：

• (A) 平均時間複雜度 O(log n)

  • 二分搜尋演算法的工作原理是每次將搜尋範圍縮小一半。在每次比較後，搜尋的資料量都會減半。
  • 因此，無論是最佳情況、平均情況還是最壞情況，二分搜尋的時間複雜度都是 O(logn)。
  • 此敘述正確。

• (B) 疊代的空間複雜度為 O(log n)

  • 二分搜尋可以透過兩種方式實現：遞迴（recursive）和迭代（iterative）。
  • 遞迴實現的空間複雜度為 O(logn)，因為每次遞迴呼叫都會在呼叫堆疊上佔用空間，堆疊深度約為 logn。
  • 迭代實現則只需固定數量的變數（例如 low、high、mid 指標），其空間使用量不會隨著輸入資料量 n 的增加而增加。
  • 因此，迭代的空間複雜度是 O(1)（常數空間），而不是 O(logn)。
  • 此敘述不正確。

• (C) 二分搜尋演算法使用常數空間，對於任何大小的輸入資料，演算法使用的空間都是一樣的

  • 如 (B) 選項所述，二分搜尋的迭代實現確實使用常數空間 O(1)。這表示無論輸入資料有多大，除了儲存輸入資料本身外，演算法使用的額外空間是固定的。
  • 此敘述在指迭代實現時正確。

• (D) 除非輸入資料數量很少，否則二分搜尋演算法比線性搜尋更快，但資料必須事先被排序

  • 速度比較：二分搜尋的時間複雜度是 O(logn)，而線性搜尋（Linear Search）是 O(n)。當資料量 n 很大時，O(logn) 顯著快於 O(n)。對於非常小的資料量，兩種演算法的實際運行時間可能差異不大，甚至由於二分搜尋的計算開銷略大，線性搜尋可能在極小資料量下表現「更快」一些（但這通常在理論複雜度分析中不予考慮）。
  • 前提條件：二分搜尋要求輸入資料必須事先是已排序的，否則無法正確工作。線性搜尋則沒有這個要求。
  • 此敘述正確，它準確地描述了二分搜尋與線性搜尋的優勢、劣勢和前提。

綜合來看，選項 (B) 對於「迭代的空間複雜度」的描述是錯誤的。

The final answer is B​
最終答案是 B​

二分搜尋演算法 (Binary Search) 的特性

• 時間複雜度

  • 最差、平均時間複雜度為 O(log n)。

  • 線性搜尋 (Linear Search) 的時間複雜度為 O(n)，所以二分搜尋通常更快（但前提是資料已排序）。

• 空間複雜度

  • 疊代 (Iterative) 實作：使用 O(1) 的額外空間（因為只需幾個變數來追蹤索引）。

  • 遞迴 (Recursive) 實作：會使用遞迴堆疊，最差情況下會佔 O(log n) 的額外空間（因為每次呼叫會佔用一個函式堆疊幀）。