二元搜尋(Binary Search)演算法又稱為二分搜尋(Half-Interval Search)演算法或是對數搜尋(Logarithmic Search)演算法,顧名思義,這套演算法的核心思想就在於「二分」,可以在已排序好的序列中進行高效率的搜尋。



二元搜尋法(Binary Search)

二元搜尋法的概念

相對於先前介紹過的線性搜尋法,二元搜尋法不需要把集合中的元素一個一個拿出來判斷,因為它所搜尋的集合必須是已經排序好的序列,所以可以直接利用元素的大小來決定下次要尋找的位置。

在一個已排序好的序列中搜索元素是一件輕鬆容易的事情,我們可以先設定搜索範圍,每次都用這範圍最中間的元素來與要查找的目標元素比大小,如果要查找的目標元素比較大,表示如果目標元素存在於該序列中的話,其一定是位在目前範圍的後半段(值大的那段);反之,如果要查找的目標元素比較小,表示如果目標元素存在於該序列中的話,其一定是位在目前範圍的前半段(值小的那段)。在下次搜尋的時候,也是一樣拿目標元素與前半段或是後半段的正中央元素進行比較,如此反覆動作,直到找出相同的元素為止;或者直到查找範圍只有一個元素時,表示要找的元素並不存在於序列中。

二元搜尋法的過程

假設現在有個已排序好的整數陣列,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

然後我們要用二元搜尋法來找到元素69。這邊可以看到此陣列的長度為10,是偶數,所以並不能剛好選到正中間的元素,不過這也沒關係,選擇索引4或是索引5都可以,在此以索引4為例。

       ●              ○                  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                     69 > 38

由於我們要找的元素69比索引4的元素值38還要來得大,因此可以知道若元素值69存在於該陣列的話,那麼它一定是在索引值大於4的位置,索引值小於4的元素們就都不用去管了。所以下一次搜尋,我們要選擇索引5到索引9的中間元素,也就是索引7

                           ●      ○      ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                                69 == 69

如此一來就找到元素69了,其存在於陣列中的索引7的位置。如何?夠快吧!

binary-search

二元搜尋法的程式實作

在實作程式的時候,應該要避免使用遞迴(Recursive)的結構,因為遞迴需要不斷地重新建構函數的堆疊空間,硬體資源的負擔會比較大,且若是遞迴層數過多還會導致堆疊溢出(Stack Overflow)。所以比較好的做法還是在一個函數內以迴圈迭代的方式來完成。

二元搜尋法的複雜度

以#{{n}}#來表示要搜尋的資料筆數。

項目備註
最差時間複雜度#{{O(\log n)}}#元素不在序列中,或者是二分到不能再分時才被發現。
最佳時間複雜度#{{O(1)}}#要查找的元素剛好位於序列的中間。
平均時間複雜度#{{O(\log n)}}#
額外最差空間複雜度(遞迴)#{{O(\log n)}}#
額外最差空間複雜度(迭代)#{{O(1)}}#