演算法知識 - Binary Search 二分搜尋

Binary Search 介紹與應用

Binary Search 是我們常見的搜尋方式，相對簡單但也非常使用的演算法，其使用方式需要先在一個經過排序的陣列中找出我們想找出的值。

時間複雜度是 \(O(\log n)\)

應用類型相當廣泛，在常見的資料型態中都可以見到

Binary Search 原理

在一個有排序的陣列中，假設我們要找出的是 x，找出最中間的值，與 x 進行比較，如果比中間的值大，那我們只需要再從此陣列中區間範圍 [ Mid , Right ] 即可，為甚麼可以這樣子呢？

因為是經過排序的，所以表示我們只要再往右邊的那些數值再去查詢，同樣地，如果比中間的值小那我們就只需要在從 [ Left , Mid] 去找即可。

其中 \( mid = (Left + Right ) / 2 \)

舉例一下，我們要在數列中 10 20 30 40 50，找出 1，要怎麼做呢？
P.S. 這裡的 index 從 1 開始

Step1 : 這時 Left = 1 , Right = 5 ，找出此數列的中間值 30，並跟 10 比較

\( Mid = (Left + Right ) / 2 = 3 \)
由於 10 < 30，所以我們接下來要搜尋的範圍就是 \( [left=1 , Right=3 ] \)

Step2 : 這時 Left = 1 , Right = 3 ，找出此數列的中間值 20，並跟 10 比較

\( Mid = (Left + Right ) / 2 = 2 \)
由於 10 < 20，所以我們接下來要搜尋的範圍就是 \( [left=1 , Right=2 ] \)

Step3 : 這時 Left = 1 , Right = 2 ，找出此數列的中間值 10，並跟 10 比較

\( Mid = (Left + Right ) / 2 = 1 \)，這裡是採用 C++，C++ 在整數除法時會無條件捨去。
由於 10 == 10，我們就可以知道我們想找的值在此數列中的 1 號位置。

Situation: 在寫二分搜尋時一些小注意

值得提醒的是，二分搜尋法固然簡單，但常常會有一些小問題自己沒有注意到，因此如果是系統已經有內建好的函數盡量使用系統內建函數會相對輕鬆一些。簡單來說就是套件保證沒有 bug，但我不敢保證自己沒有 bug

容易出現的問題：數列中有重複的值，我想要的是找出此數列中大於 or 小於此數字的值

C++ 語法介紹

在 C++ 中已經有函數可以方便我們直接套用分別是：

• lower_bound 找出此數列中第一個數值是大於等於想查詢的值
• upper_bound 找出此數列中最後一個數值是大於等於想查詢的值
  詳細用法請看 C++ Refence 或是 STL源码学习—-lower_bound和upper_bound算法

如果看不太懂文字說明，可以看看這張圖，我想就了解了：

Binary Search 實作與說明

在程式碼進行說明，相信會比較好理解些。

找出此數列中第一個數值是大於等於想查詢的值，類似於 C++ 的 lower_bound

#define N 
int num[n] //以排序過且要進行查詢的數列

int bs(int l , int r , int v){ //bs binary search , l =left , r= right , v = value
    int m ; // m = mid 
    while(r>l){ // 假如 r > 1 表示尚未二分搜尋完畢
        m = (r+l) / 2 ; // m 找出中間值 
        if(num[v] > num[t[m]] ) l = m+1 ; //如果要查詢的值大於中間值，那範圍將被改成[M id , Right]
        //但因為 mid 已經有被查詢過因此 mid +1
        else r = m ;
        //如果沒有那範圍則被改成 [Left , Mid]，沒有做 mid -1 是因為有可能是要查詢的值與 mid 值相同
    }
    return r ; //回傳被查詢到的值
}

找出此數列中最後一個數值是大於等於想查詢的值，類似於 C++ 的 upper_bound

讀者在觀看此程式碼前，必須先將前一個程式碼熟悉。

稍微要記住的是，這裡的區間範圍是 \( [ left , Right) \)

#define N 
int num[n] //以排序過且要進行查詢的數列
int bs(int l , int r , int v){ //bs binary search , l =left , r= right , v = value
    int m ;  // m = mid 
    while(r > l){ // 假如 r > 1 表示尚未二分搜尋完畢
        m = (l+r) / 2 ; // m 找出中間值 
        if(num[m] <= v) l = ++m; //與上份程式碼章節相同
        //值得注意的是，因為區間範圍是 [ Mid , Right )，我們要防範 Right = mid 時，
        //會造成錯亂，於是我們先幫 mid+1，之後再減回來
        else r = m; //與上份程式碼章節相同 
        //值得注意的是，因為區間範圍是 [ Left , Mid )，但因為 C++ 在計算 mid 時小數會捨取，
        //因此如果我們只要讓 else 只處理 中間值 > 查詢值，就不會造成錯亂
        //我們在下方將會進行舉例，代號為 Q-A
    }
    return m-1 ; //為甚麼要 m-1？
    //因為
}

Q-A

舉例：
L = 1 , R = 2 , M = 1 ，進入 if statement ， L = 2 , M = 2，此時區間是向 R 靠近，但 R 是 ) 會超出查詢範圍，因此必須要 -1。
L = 1 , R = 2 , M = 1 ，進入 else statement ， R = 1 , M = 1，此時區間是向 L 靠近，L 本身範圍是 [，因此沒有問題。

主要就是這個樣子，希望讀者都能看懂XD。

未來如果我還有寫更多版本，我將會放上

Binary Search 應用

• UVa957 - Popes (Binary Search)

參考連結

STL源码学习—-lower_bound和upper_bound算法
std::lower_bound
二分搜尋演算法

心得

二分搜尋好多毛病要解決，真麻煩，好想用套件XD，其實此演算法在我高中時就已經學會了，為甚麼會想打這一篇呢？主要是因為想要幫自己的演算法建立模板，方便未來的我用上，也害怕假如未來的我以後忘記怎麼寫時就在也真的想不起來了，因為找不到過去讓我參考，希望未來的我還能記住，也希望看到此篇的讀者不會忘記。

寫 Blog 真的非常吃力不討好，真的好累又好麻煩，學習速度比別人慢，別人可以在你打 Blog 的時間學習更多演算法、更多知識，那你為甚麼還要打呢？因為我笨，我學習差，我需要讓瞭解演算法的自己來幫助未來可能會遺忘此演算法的自己，幫助他，讓我的未來不遺失我的過去。

Binary Search 無助解程式碼

這裡則放置沒有註解的程式碼，如果讀者想要複製就從這裡進行複製吧！

找出此數列中第一個數值是大於等於想查詢的值，類似於 C++ 的 lower_bound

#define N 
int num[n] 

int bs(int l , int r , int v){
    int m ;
    while(r>l){
        m = (r+l) / 2 ;
        if(b[v] > b[t[m]] ) l = m+1 ;
        else r = m ;
    }
    return r ;
}

找出此數列中最後一個數值是大於等於想查詢的值，類似於 C++ 的 upper_bound

讀者在觀看此程式碼前，必須先將前一個程式碼熟悉。

稍微要記住的是，這裡的區間範圍是 \( [ left , Right) \)

#define N 
int num[n] 
int bs(int l , int r , int v){
    int m ;
    while(l < r){
        //debug
        //cout << num[l] << ' ' << num[r] << '\n' ;
        m = (l+r) / 2 ;
        if(num[m] <= v) l = ++m;
        else r = m;
    }
    return m-1 ;
}