民國114年 第2梯次 電腦軟體設計(C++)乙級 學科
第58題
資料共有4096 筆,若採用二元搜尋法(Binary Search),最差情況下需搜尋幾次才能找到一筆已知 的資料?
題目
資料共有4096 筆,若採用二元搜尋法(Binary Search),最差情況下需搜尋幾次才能找到一筆已知 的資料?
- (1) 12
- (2) 14
- (3) 11
- (4) 13
官方答案
(4) 13
解析
二元搜尋法每次比較將搜尋範圍對半切分，最差情況（目標在最後一次比較才命中或確定不存在）所需次數公式為⌊log₂n⌋+1。本題n=4096=2¹²，代入得⌊log₂4096⌋+1=12+1=13次。亦可用遞迴T(2^k)=k+1驗證：T(4096)=T(2¹²)=13，故選項4（13）正確。選項1（12）少算最後一次對剩餘單一元素的確認比較；選項2、3數值不符。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。