Contents
  1. 1. Binary Search
    1. 1.1. 概念
    2. 1.2. 範例
    3. 1.3. 複雜度
    4. 1.4. Code
    5. 1.5. 參考資料:

概念

一種非常有效率的搜尋演算法,但前提是”要被搜尋的數列”必須要是已排序好的。這邊以由小排到大的數列來做例子,搜尋的概念是拿數列最中間的數來與要搜尋的目標值做比較,比較結果只有三種:大於、小於、等於。由於數列已經事先排序好的,所以,各個比較結果代表的是:

    1. 目標值 < 中間數

代表要搜尋的目標值在中間數的左邊,下次搜尋範圍可縮減成只有左半邊

    2. 目標值 > 中間數

代表要搜尋的目標值在中間數的右邊,下次搜尋範圍可縮減成只有右半邊

    3. 目標值 等於 中間數

已經找到目標值,所以演算法可以結束了

而每次搜尋的概念都相同:拿中間數做比較,若相同就結束,若不同就縮小搜尋範圍,演算法會依此概念一直循環,直到找到目標值為止。

最中間的數是 (開頭index + 結尾index) / 2 的值

範例

以下圖來做例子,我們要在陣列中找目標值4,此陣列的範圍0~8,最中間的位置是 (0+8)/2 = 4,值是7
所以拿7來比較
因為 4 < 7,所以搜尋範圍縮小變成只有左半邊(0~3的位置),中間的位置是(0+3)/2 = 1(取整數)
所以拿2來比較
因為 4 > 2,所以搜尋範圍縮小變成只有右半邊(2~3的位置),中間為(2+3)/2 = 2(取整數)
所以拿4來比較
因為 4 == 4,找到目標值,演算法結束

複雜度

時間 : 由於每次搜尋的範圍都減少一半,所以時間複雜度是O(log n)。
Best : O(1)
Average : O(log n)
Worst : O(log n)

空間 : O(1)

Code

See my code on github.

參考資料:

Binary search algorithm wiki