概念

二分搜尋是一種在已經排序過的資料中快速找到目標資料的高效率的演算法。這個方法建立在一個基本的觀念上：將資料集一分為二，然後根據目標資料與中間元素的大小比較，決定繼續搜尋左半部分或右半部分，如此反覆進行，直到找到目標資料或確定其不存在。

如果上述內容不太容易理解，可以想像一本書，當你想找尋第 頁時，你可以開啟書本的中間頁，如果目標頁數大於中間頁，則繼續在右半部分搜尋，反之則在左半部分搜尋，這樣的步驟持續進行，最終你會迅速找到第 頁。

實作

以下先用 pseudo code 來讓大家比較好理解

initialize left,right;
while(there are more integers to check){
    let a[middle] be the middle element
    if x < middle,right = middle - 1
    if x = a[middle],return middle
    if x > middle,left = middle + 1
}
return -1;

基本上，你需要先定義左界和右界，然後在循環中不斷找尋左界和右界之間的中間元素是否符合目標資料。如果不符合，則更新左界或右界，如果符合，則直接返回該位置。接下來，讓我們使用 C++ 程式碼示範實作：

int binary_search(int arr[],int x,int left,int right){
    int middle;
    while(left < right){
        middle = (left + right) / 2;
        if(arr[middle] > x){
            right = middle - 1;
        }else if(arr[middle] == x){
            return middle;
        }else if(arr[middle] < x){
            left = middle + 1;
        }
    }
    return -1;
}

複雜度分析

我們可以看到，每次迭代都將搜尋範圍一分為二，且比較次數很少，因此非常高效率。時間複雜度因為每次迭代都是將範圍二分，所以是對數時間複雜度，表示為 。不過，需要注意的是，如果在使用二分搜尋之前需要對資料進行排序，那麼整體時間複雜度可能會增加到

總結 & 預告

上述內容概括了二分搜尋的基本概念、實作方法以及複雜度分析。然而，二分搜尋的重要性尚未完全展現。在明天的文章中，我們將透過實際解決問題，來講解二分搜尋的使用條件和解決問題的實際應用。