二元搜尋法

 

方法；

  將target與已排序陣列的中間項比對，若大於，則搜尋右半段，若小於，則搜尋左半段  （小到大）

 

步驟：  (預設：left = 0, right = array size)

  1.  middle = (left + right) / 2

  2.  將target 與 arr[middle] 比較，

        大於： left = middle + 1

        小於： right = middle - 1

  3.  重複步驟1直到找到target或結束   （left > right）

 

 

 

複雜度：

  最佳時間複雜度： O（1）    （target = 中間項）

  平均時間複雜度： O（log n）  (因為對半切，此處的log底數為2)

  最差時間複雜度： O（log n）

  空間複雜度： O（1）   （middle , left , right （常數個） ）

arrow
arrow
    全站熱搜

    大神（偽） 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄