民國100年 乙級專案 電腦硬體裝修乙級 學科
第46題
將1000 個已排序過後資料,利用二分搜尋法( B i n a r y S e a r c h ) 找尋其中一筆特別資料,最多 要搜尋比較幾次?
題目
將1000 個已排序過後資料,利用二分搜尋法( B i n a r y S e a r c h ) 找尋其中一筆特別資料,最多 要搜尋比較幾次?
- (1) 10
- (2) 11
- (3) 55
- (4) 100
官方答案
(1) 10
解析
二分搜尋法每次將搜尋範圍對半切割，最多比較次數公式為 ⌈log2(n+1)⌉ 或 floor(log2(n))+1。代入 n=1000，log2(1000)≈9.97，⌈log2(1001)⌉=⌈9.97⌉=10。亦可逐次驗算：1000→500→250→125→63→32→16→8→4→2→1，共 10 次。故最多搜尋比較 10 次，選項 1 正確。選項 2 的 11 次過多；選項 3、4 的 55、100 並非二分搜尋結果。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。