moea_joint
105年
[資訊] 計算機原理、網路概論
第 14 題
某陣列中若含有62筆資料，且已由小至大排序完成，若要由此陣列中尋找某一筆資料，則以二元搜尋法最多需比較幾次？
- A 7次
- B 6次
- C 5次
- D 4次
思路引導 VIP
想像你有一本編好頁碼的字典，每一次你翻開目前範圍的正中間那一頁，都能幫你排除掉剩下的一半頁數。如果這本字典有 62 頁，且每一次動作都讓搜尋範圍減半，你覺得大約要經過幾次「對半砍」的操作，範圍才會縮小到只剩下最後唯一的一頁呢？
🤖
AI 詳解
AI 專屬家教
二元搜尋法的效率核心
恭喜你答對了！這題考驗的是你對分治法 (Divide and Conquer) 效率的直覺。在已排序的資料中，二元搜尋法每次比較都能排除掉一半的資料。對於 $n$ 筆資料，其最大比較次數可由 $2^k \ge n$ 的最小整數 $k$ 來決定。以本題的 62 筆資料為例，我們觀察 $2$ 的次方項： $$2^5 = 32 < 62$$
▼ 還有更多解析內容