Q223.
關於二分搜尋法(Binary Search)，下列那些正確？
電腦軟體設計共同科目 · 乙級 · Q223
難易度分析
3 / 5
本題採複選形式，要求全面掌握二分搜尋法的前置條件、時間複雜度及適用範圍。由於選項中包含了容易混淆的排序方向限制與資料型別適用性等陷阱，考生必須精確區分核心概念與細節誤區才能正確作答。
正確答案 (複選)：②, ③
- ② 可用陣列(Array)作為二分搜尋法的資料結構:陣列(Array) 支援隨機存取(Random Access)，可在 O(1) 時間內直接存取中間元素，是實作二分搜尋法的理想資料結構。
- ③ 在最壞情形下，所需比較次數為O(logn)，其中n 為資料數量:二分搜尋法每次比較後將搜尋範圍縮減一半，因此在最壞情況下的時間複雜度為 O(log n)，其中 n 為資料筆數。
錯誤選項解析
- ① 使用二分搜尋法之前，需先將資料排序，而且必須是由小至大:二分搜尋法確實需要資料先經過排序，但排序方向可為遞增或遞減皆可，並非限定由小至大。只要資料具有一致的順序性，搜尋時即可依比較結果決定往左或往右縮小範圍。
- ④ 二分搜尋法適用於數字的搜尋，但不適用於字串的搜尋:二分搜尋法適用於任何可比較大小的資料型別，包含字串。字串可依字典序(Lexicographical Order)進行排序與比較，因此同樣能使用二分搜尋。
Learning Tip
"此題常考陷阱在於混淆「排序必要性」與「排序方向限制」，以及誤認二分搜尋僅限數值型別。需牢記二分搜尋的兩大前提：資料已排序與支援隨機存取，故鏈結串列(Linked List) 不適合直接實作二分搜尋。實務上，遞增或遞減排列均可執行二分搜尋，只需調整縮小範圍的判斷邏輯即可。"
學員答題分佈
①使用二分搜尋法之前，需先將資料排序，而且必須是由小至大0%
②可用陣列(Array)作為二分搜尋法的資料結構0%
③在最壞情形下，所需比較次數為O(logn)，其中n 為資料數量0%
④二分搜尋法適用於數字的搜尋，但不適用於字串的搜尋0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！