普考-資訊處理計算機概要107 年第 40 題單選題
有一已排序數列，使用二元搜尋法最壞的時間複雜度為何？
AO(1)
BO(n)
CO(logn)正確答案
DO(nlogn)
C正確答案
二元搜尋法利用已排序的特性，每次比對後將搜尋範圍縮減一半，最壞情況下需進行 log₂n 次比對，故時間複雜度為 O(log n)。
為什麼答案是 C
二元搜尋法每次將資料量除以 2，最壞情況下（找不到目標或目標在最後一次分割才出現）分割到剩 1 個元素，需 log₂n 次，即 O(log n)。
載入中…
完整詳解
Pro · 無限重點 二元搜尋法利用已排序的特性，每次比對後將搜尋範圍縮減一半，最壞情況下需進行 log₂n 次比對，故時間複雜度為 O(log n)。
關鍵字「二元搜尋」+「最壞情況」。每次範圍砍半對應的數學運算就是對數 (log)，秒選 O(log n)。
逐選項分析
A✕ 陷阱
O(1) 是二元搜尋法的「最佳情況」（第一次比對就剛好命中中間值），或者是理想狀態下雜湊表 (Hash Table) 的搜尋時間。
B✕
O(n) 是循序搜尋法 (Linear Search) 的最壞情況，代表必須從頭到尾把所有元素都檢查過一遍。
C✓ 正確
二元搜尋法每次將資料量除以 2，最壞情況下（找不到目標或目標在最後一次分割才出現）分割到剩 1 個元素，需 log₂n 次，即 O(log n)。
D✕
O(n log n) 通常是高效率比較型排序演算法（如合併排序 Merge Sort、堆積排序 Heap Sort）的時間複雜度，而非搜尋演算法。
常見搜尋演算法時間複雜度比較
| 演算法 | 前提條件 | 最佳情況 | 最壞情況 |
|---|
| 循序搜尋 (Linear Search) | 無 (未排序也可) | O(1) | O(n) |
| 二元搜尋 (Binary Search) | 必須已排序 | O(1) | O(log n) |
| 雜湊搜尋 (Hash Search) | 需建立雜湊表 | O(1) | O(n) (發生嚴重碰撞時) |
考選部常把「最佳情況」與「最壞情況」混在一起考。二元搜尋的最佳情況是 O(1)（剛好在正中間），但題目問的是「最壞情況」（找不到或在邊緣），作答時務必看清題目要求的是 Best case 還是 Worst case。 
