二分法(二元搜尋樹)(Binary Search Tree) 簡介 – jashliao部落格

二分法(二元搜尋樹)(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（次）