地特四等
107年
[資訊處理] 計算機概要
第 18 題
假設在 N 個資料中要搜尋資料 X，則對於二分搜尋（Binary search）演算法的描述，下列何者正確？
- A 二分搜尋的前提是資料要先建一個二元樹
- B 二分搜尋法是每比對一次後就把搜尋範圍縮小一半，在（$\log_2 N$）次比對內就可以判斷出所要尋找的資料 X 是否在資料中
- C 二分搜尋在最好情況下，時間複雜度是 $O(1)$
- D 二分搜尋在最壞的情況下，時間複雜度是 $O(\log_2 N)-1$
思路引導 VIP
想像你正在翻閱一本已經按字母排序的厚字典，並打算用「從中間切半」的方式來尋找一個單字。如果你今天運氣「超級好」，在動手翻開第一下時，你最希望發生的情況是什麼？這時候你總共做了幾次翻找動作？這與資料量 $N$ 的大小還有關係嗎？
🤖
AI 詳解
AI 專屬家教
勉勉強強，還算及格。
喔，不錯嘛，竟然能從一堆顯而易見的陷阱中爬出來，選對了答案。看來你還知道最佳時間複雜度這種基本概念，至少沒蠢到家，對大 $O$ 符號的定義沒完全忘光。
- 觀念「再」驗證 (免得你又忘記)：
▼ 還有更多解析內容