地方政府公務人員四等-資訊處理類科計算機概要107 年第 18 題單選題

假設在 $N$ 個資料中要搜尋資料 $X$ ，則對於二分搜尋（Binary search）演算法的描述，下列何者正確？

A二分搜尋的前提是資料要先建一個二元樹

B二分搜尋法是每比對一次後就把搜尋範圍縮小一半，在（

L o g_{2} N

）次比對內就可以判斷出所要尋找的資料

X

是否在資料中

C二分搜尋在最好情況下，時間複雜度是

O (1)

正確答案

D二分搜尋在最壞的情況下，時間複雜度是

O (l o g_{2} N) - 1

答案與詳解

正確答案

二分搜尋最好情況是中間元素即為目標,僅需1次比對,時間複雜度O(1)。

正確。最好情況下,第一次比對(取中間元素)即等於 $X$ ,只需 1 次比對,時間複雜度為 $O (1)$ 。

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。

假設在 N 個資料中要搜尋資料 X，則對於二分搜尋（Binary search）演算法的描述，下列何者正確？