Zi 字媒體

二分法(二元搜尋樹)(Binary Search Tree)  簡介 文字解釋:     就是一組有序的數字裡面選一個目標值（target），然後你會定義一個start指針，end指針和mid指針，然後每次比較mid和target的大小     如果target大的話，說明我要找的目標其實是在這組有序數組裡面的後半部分，那麼我就可以直接拋棄掉前一半數據了，每次一半一半的扔好爽啊～直到最後確認target的位置。 時間複雜度:     log(n):     因為如果有一組有序的數組裡面有N個數字，那麼按照我上面找目標值的思路，第一次篩掉一半，第二次再篩掉一半，第三次…..     我們假設篩了k次，最後終於找到了那個target,所以我們可以得到公式     也就是N*(1/2)^k = 1，那麼我們的k是多少咧？也就是我們篩選的次數     （噹噹噹噹～）k=log(n)     PS.         如果你要在100億個有序的數字裡面找到你想要的那個target，通過二分法只需要33次足以～         Log2(10000000000) ~ 33.219281（次）