二元搜尋法
方法；
將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 （常數個） ）
全站熱搜
留言列表
進階程式設計 (C++) (2)