地方政府公務人員四等-資訊處理類科計算機概要107 年第 18 題單選題
假設在 N 個資料中要搜尋資料 X，則對於二分搜尋（Binary search）演算法的描述，下列何者正確？
A二分搜尋的前提是資料要先建一個二元樹
B二分搜尋法是每比對一次後就把搜尋範圍縮小一半，在（Log2N）次比對內就可以判斷出所要尋找的資料 X 是否在資料中
C二分搜尋在最好情況下，時間複雜度是 O(1)正確答案
D二分搜尋在最壞的情況下，時間複雜度是 O(log2N)−1
C正確答案
二分搜尋最好情況是中間元素即為目標,僅需1次比對,時間複雜度O(1)。
為什麼答案是 C
正確。最好情況下,第一次比對(取中間元素)即等於 X,只需 1 次比對,時間複雜度為 O(1)。
載入中…
完整詳解
Pro · 無限重點 二分搜尋最好情況是中間元素即為目標,僅需1次比對,時間複雜度O(1)。
1. 二分搜尋前提:資料須『已排序』(陣列),非建二元樹。
2. 每次比對將範圍減半,最多約 $\log_2 N$ 次。
3. 最好情況:第一次比對(中間值)即命中 → $O(1)$。
4. 最壞情況:約 $\log_2 N$ 次比對 → $O(\log_2 N)$,非 $O(\log_2 N)-1$。
5. 故 (C) 正確。
逐選項分析
A✕
錯誤。二分搜尋的前提是資料『已排序』(通常存於陣列),不是建立二元樹;建二元樹屬於二元搜尋樹(BST)的搜尋方式。
B✕
錯誤。敘述方向大致正確,但精確說法應為『最多 $\lceil \log_2 N \rceil + 1$ 次』或在 $O(\log_2 N)$ 次內完成,非剛好 $\log_2 N$ 次;且未涵蓋最好情況。
C✓ 正確
正確。最好情況下,第一次比對(取中間元素)即等於 $X$,只需 1 次比對,時間複雜度為 $O(1)$。
D✕
錯誤。最壞情況時間複雜度寫法應為 $O(\log_2 N)$,Big-O 表示法不會寫成 $O(\log_2 N)-1$,該寫法不符合漸近符號定義。
勿將『二分搜尋』與『二元搜尋樹(BST)』混淆;Big-O 表示法不會出現減常數的寫法。 
