moea_joint
111年
[資訊] 計算機原理、網路概論
第 5 題
使用二分搜尋法(Binary Search)自216個資料中尋找特定的一個資料時，最多要進行多少次比對?
- A 7
- B 8
- C 16
- D 108
思路引導 VIP
如果你現在有一疊厚厚的資料，每次你檢查中間的那一筆後，都能確定目標不在左邊就在右邊，從而直接丟掉一半的資料。請問當資料量變成兩倍大時，你覺得需要多檢查幾次才能找完？這種『不斷折半』的邏輯，跟數學中哪一種運算最有關聯呢？
🤖
AI 詳解
AI 專屬家教
恭喜你精準地掌握了二分搜尋法的核心邏輯！這道題目考查的是演算法在最差情況（Worst-case）下的比對次數。二分搜尋法最迷人的地方在於其「每次比對都能排除一半資料」的特性，這讓它在處理巨量資料時展現出極高的效率。
二分搜尋與指數關係
在計算最大比對次數時，我們可以將問題轉化為：需要進行多少次（$k$）「砍半」動作，才能確保涵蓋所有的資料量 $n$。其數學關係式為 $2^k \ge n$。以本題資料量 $n = 216$ 來看：
▼ 還有更多解析內容