普通考試
115年
[電信工程] 計算機概要
第 22 題
關於循序搜尋（Sequential search）和二元搜尋（Binary search）的敘述，下列何者錯誤？
- A 若排序好的資料以陣列（Array）存放，可利用二元搜尋從中尋找資料
- B 若排序好的資料以鏈結串列（Linked list）存放，可利用循序搜尋從中尋找資料
- C 若排序好的資料以陣列存放，可利用循序搜尋從中尋找資料
- D 若排序好的資料以鏈結串列存放，可利用二元搜尋從中尋找資料
思路引導 VIP
請試著想像：如果你在一排貼有編號的置物櫃中找東西（陣列），你可以直接走向編號 $50$ 的櫃子；但如果你正在玩一場「尋寶遊戲」，每一關的線索都藏在下一個關卡裡（鏈結串列），你有可能在不知道中間關卡位置的情況下，直接跳過前面的關卡去檢查中間那一關嗎？這對你執行「砍半搜尋」的策略會產生什麼影響？
🤖
AI 詳解
AI 專屬家教
資料結構與隨機存取（Random Access）的關聯
恭喜你精準地捕捉到了演算法與資料結構之間的「匹配性」。這道題目的核心在於理解二元搜尋（Binary Search）的高效能，是建立在能夠「立即跳轉」至中間索引的能力上。在工程實務中，我們稱之為隨機存取（Random Access）。陣列（Array）在記憶體中是連續配置的，因此我們可以透過索引值在 $O(1)$ 時間內找到中間元素；然而，**鏈結串列（Linked list）**的特性是各節點散落在記憶體中，必須透過指標（Pointer）循序走訪，要找到中間節點必須花費 $O(n)$ 的時間，這使得二元搜尋法的效率優勢蕩然無存。
演算法的實務選擇與鑑別度
▼ 還有更多解析內容