Q222.
關於二分搜尋法(Binary Search)，下列那些正確？
電腦軟體設計共同科目 · 乙級 · Q222
難易度分析
3 / 5
本題為複選題，要求對二分搜尋法的前置條件、適用資料結構及時間複雜度等多個核心概念進行全面判定，且需區分相似但原理不同的搜尋演算法，增加了認知負荷。
正確答案 (複選)：①, ③
- ① 使用二分搜尋法之前，需先將資料排序:二分搜尋法的核心前提是資料必須已排序，如此才能透過比較中間元素來決定搜尋方向，將搜尋範圍每次縮減一半。
- ③ 在最佳情形下，一次比較就可找到所欲搜尋的資料:最佳情況下，目標元素恰好位於陣列中間位置，僅需一次比較即可找到，時間複雜度為 O(1)。
錯誤選項解析
- ② 可用鏈結串列(Linked List)作為二分搜尋法的資料結構:鏈結串列不支援隨機存取（Random Access），無法在 O(1) 時間內定位中間元素，因此不適合用於二分搜尋；二分搜尋應使用陣列等支援索引存取的資料結構。
- ④ 雜湊(Hashing)是二分搜尋法的一種實作方式:雜湊搜尋是透過雜湊函數直接計算儲存位置，與二分搜尋法的原理完全不同；兩者屬於獨立的搜尋演算法，雜湊的平均搜尋時間為 O(1)，但需處理碰撞問題。
Learning Tip
"此題常考二分搜尋法的適用條件與時間複雜度。易混淆點：二分搜尋要求資料已排序且需支援隨機存取，故不適用於鏈結串列；雜湊與二分搜尋是兩種不同的搜尋策略，不可混為一談。二分搜尋的平均與最壞時間複雜度均為 O(log n)，最佳情況為 O(1)。"
學員答題分佈
①使用二分搜尋法之前，需先將資料排序0%
②可用鏈結串列(Linked List)作為二分搜尋法的資料結構0%
③在最佳情形下，一次比較就可找到所欲搜尋的資料0%
④雜湊(Hashing)是二分搜尋法的一種實作方式0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！