18 假設在N個資料中要搜尋資料X，則對於二分搜尋（Binary search )演算法的描述，下列何者正確？
(A) 二分搜尋的前提是資料要先建一個二元樹
(B)二分搜尋法是每比對一次後就把搜尋範圍縮小一半，在（Log2N)次比對內就可以判斷出所要尋找的資 料X是否在資料中
(C) 二分搜尋在最好情況下，時間複雜度是0(1)
(D)二分搜尋在最壞的情況下，時間複雜度是0(log2N)-1

答案：登入後查看
統計： A(46), B(254), C(447), D(37), E(0) #1916505

詳解 (共 8 筆)

#3264921
二分搜尋法係為在以排序好的元素集合中，尋...
(共 63 字，隱藏中）
前往觀看
12
-1
#3638357
(B)判斷X是否在資料中的 最差情況:在...
(共 130 字，隱藏中）
前往觀看
6
0
#3836482
Binary search 最多搜尋:...
(共 139 字，隱藏中）
前往觀看
4
0
#4119761

B是錯在 "⌈log (N+1)⌉" 或者是 "⌊(logN)⌋+1" 次內才可以判斷出所要尋找的資料X是否在資料中，所以選項少算 1 次


舉個例子就知道

 ⌈log (3+1)⌉  = ⌊(log3)⌋+1 = 2 

O O O <- 三筆資料最多找 2 次 

　↑↑

    1  2


⌈log (4+1)⌉  = ⌊(log4)⌋+1 = 3

O O O O <- 四筆資料最多找 3 次

　↑↑↑
    1  2  3

4
0
#3171834
C第一次就搜尋到
(共 10 字，隱藏中）
前往觀看
2
0
#3456680

B哪裡錯?? 運氣好1次找到也是在Log2N內阿


0
1
#3467450
平均是O(N)最佳是O(log2(N))...
(共 61 字，隱藏中）
前往觀看
0
4
#3454400

B是平均，D最久就是N

C最短一次

0
1