資料共有4096 筆,若採用二元搜尋法(Binary Search),最差情況下需搜尋幾次才能找到一筆已知 的資料?

題目

資料共有4096 筆,若採用二元搜尋法(Binary Search),最差情況下需搜尋幾次才能找到一筆已知 的資料?

1. (1) 13
2. (2) 14
3. (3) 11
4. (4) 12

官方答案

(1) 13

解析

二元搜尋法每次比較都把搜尋範圍縮小一半，最差情況的比較次數為 ⌊log₂n⌋+1。本題 n=4096=2¹²，代入得 log₂4096=12，故最差需 12+1=13 次比較才能確定找到或確定不存在。可反向驗證：13 次比較最多可涵蓋 2¹³=8192 筆，足以包含 4096 筆；而 12 次僅能涵蓋 2¹²=4096 筆，邊界情況仍可能不足，因此 11、12 都偏少，14 則超出實際需要，正確值為 13 次。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF