[理工] [DS]binary search

[jim055006 (jim)]

True or False

(1)When there is duplication among primary keys, binary search can be used.

True.

(2)The time complexity of binary search is the same as searching with binary
   search tree.

False.

------------------------------------------------------------------------------

我的疑問:

第一題,我不懂他到底在講甚麼,有沒有好心人可以幫我翻一下XD

第二題,不都一樣是Ο(㏒n)??...還是說連Worst Case 也要考慮進去??


以上...
有請高手幫忙解答....
鋼溫!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 223.139.214.182
推 imrod:第二題不是true嗎@@?
→ jim055006:= ="...我打錯了是FALSE...抱歉
※ 編輯: jim055006       來自: 223.139.214.182      (11/06 00:07)
推 mqazz1:(2) binary search: O(logn), BST若skew: O(n)
→ jim055006:所以連worst case也要考慮進去= ="...真煩人XD
→ mqazz1:除非是balance的BST 搜尋才會是O(logn)
→ jim055006:對ㄝ....感謝M大都幫我解題...您是在全國電子打工的吧!
推 mqazz1:全國電子@@? 沒有耶..
→ jim055006:M大我上面那提還有疑問...
推 Delion:好像是在問當有重複的Key值時，可不可以使用Binary Search?
→ jim055006:喔喔....了解...謝謝D大~~
→ sneak: 對ㄝ....感謝M大都 https://daxiv.com