民國103年 第2梯次 電腦硬體裝修乙級 學科
第41題
將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) 55
- (3) 11
- (4) 100
官方答案
(1) 10
解析
二分搜尋法每比較一次就把搜尋範圍縮小一半，n 筆已排序資料最多比較 ⌈log₂n⌉ 次。代入 n＝1000，log₂1000 ≈ 9.97，取上界為 10；也可用 2⁹＝512＜1000 ≤ 2¹⁰＝1024 驗證，因此最多 10 次。55 是 1 到 10 的累加值，100 只是資料量的一成，兩者都與比較次數無關。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。