Q83.
資料共有4096 筆，若採用二元搜尋法(Binary Search)，最差情況下需搜尋幾次才能找到一筆已知的資料？
電腦軟體設計共同科目 · 乙級 · Q83
難易度分析
3 / 5
本題需運用特定演算法的計算公式，且選項中包含容易產生混淆的數值，要求考生必須精確掌握最差情況的判定標準，而非僅進行簡單的對數運算。
正確答案：③13
③ 13:13 次為正確答案。二元搜尋法最差比較次數公式為 ⌊log₂(n)⌋ + 1，代入 n = 4096 得 ⌊log₂(4096)⌋ + 1 = 12 + 1 = 13 次。
錯誤選項解析
- ① 11:11 次小於二元搜尋法對 4096 筆資料所需的比較次數。即使以 log₂(2048) = 11 計算，2048 筆資料的最差情況也需 12 次，故此數值明顯偏低。
- ② 12:12 次僅為 log₂(4096) = 12 的計算結果，但二元搜尋法最差情況公式為 ⌊log₂(n)⌋ + 1，需額外加上最後一次確認比較，因此 12 次並不完整。
- ④ 14:14 次高於實際所需。4096 = 2¹²，最差情況僅需 13 次即可完成搜尋，14 次屬於過度估算。
Learning Tip
"本題核心考點為二元搜尋法最差比較次數公式 ⌊log₂(n)⌋ + 1。常見陷阱是僅計算 log₂(n) 而忽略最後一次確認比較（即 +1 的部分）。需特別注意：當 n 恰好為 2 的冪次時（如 4096 = 2¹²），log₂(n) 為整數，但仍需加 1 才是最差情況的比較次數。此公式適用於已排序資料的搜尋情境，時間複雜度為 O(log n)。"
學員答題分佈
①110%
②120%
③130%
④140%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！