二分查詢

二分查詢

二分查詢（Binary Search）也叫作折半查詢，前提是查詢的順序結構是有序的，我們一般在陣列上進行二分查詢。
二分查詢就好像猜數位大小遊戲一樣。假設要數位目標值屬於 [1, 1000] 範圍內，當我們猜的數位小於這個目標值時（"Too low"），我們需要往大去猜；反之大於這個目標值時（"Too high"），我們需要往小去猜。當然這裡猜的方式並不是盲目的，我們每次都取中間值去猜，每猜一次可以縮小當前一半的範圍，這樣可以大大提高效率。二分查詢本質上也是這樣的過程，時間複雜度為 O(logn) ，在較巨量資料情況下相比線性查詢要快非常多。

我們定義一個左指標 left 標記當前查詢區間的左邊界，一個右指標 right 標記當前查詢範圍的右邊界。每次取 mid 來判斷當前取的值是否等於目標值 target。如果等於 target 就直接返回 mid ；如果小於目標值 target ，那麼將左邊界變為 mid + 1，縮小區間範圍繼續在 [mid + 1, right] 範圍內進行二分查詢，如果大於目標值 target ，那麼將右邊界變為 mid - 1，縮小區間範圍繼續在 [left, mid - 1] 範圍內進行二分查詢。

假如最後出現了 left > right 的情況，說明區間範圍大小縮小到 0 都無法找到該目標值，那麼很明顯陣列中不存在這個目標值 target，此時退出迴圈，返回 -1 。

二分查詢圖解

（1）

（2）

（3）

二分查詢程式碼

//二分查詢
int BinarySearch(vector<int> &v, int target){
    int left = 0, right = v.size() - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(v[mid] == target)
            return mid;
        if(v[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

---

二分查詢 遞迴

上面二分查詢也可以寫成遞迴的形式。大致步驟為：
（1）當前層 mid 位置元素等於目標值 target，直接 return mid；
（2）如果小於目標值，遞迴搜尋 [mid + 1, right] 範圍；
（3）如果大於目標值，遞迴搜尋 [left, mid - 1] 範圍。

//二分查詢法遞迴寫法
int BinarySearchRec(vector<int> &a, int left, int right, int target) {
    int mid = (left + right) >> 1;
    if(left <= right){
        if(a[mid] == target)
            return mid;
        if(a[mid] < target)
            return BinarySearchRec(a, mid + 1, right, target);
        else
            return BinarySearchRec(a, left, mid - 1, target);
    }
    return -1;
}

---

二分查詢 元素起始位置

查詢等於目標值的第一個位置

陣列中可能存在連續的多個位置元素都等於目標值 target ，當我們要查詢第一個出現的位置，我們需要保證查詢到位置的左邊所有元素都滿足小於 target，右邊所有元素都滿足大於等於 target。

當出現 a[mid] < target 時，說明我們要查詢的位置一定在 [mid + 1, right] 範圍內，當然也可以寫成 (mid, right] ；當出現 a[mid] >= target 時，說明要查詢的位置有可能是當前的 mid，也有可能是當前 mid 左邊的某個位置，所以此時要查詢的位置一定在 [left, mid] 範圍內。

因此，當 a[mid] < target，將 left = mid + 1 ；當 a[mid] >= target，將 right = mid。
當最後 left == right 即兩個指標相遇時退出迴圈，最後要判斷一下相遇位置處的元素是否等於目標值 target。如果等於目標值，就返回 left 或者 right，如果不等於目標值，說明不存在該元素，那麼就返回 -1 。

查詢等於目標值起始位置圖解

（1）

（2）

（3）

（4）

查詢等於目標值起始位置程式碼

int BinarySearchfirst(vector<int> &v, int target){
    int left = 0, right = v.size() - 1;
    while(left < right){
        int mid = (left + right) >> 1;
        if(v[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return v[left] == target ? left : -1;
}

---

二分查詢 元素終止位置

查詢等於目標值的最後一個位置

當我們要查詢最後一個出現的位置，我們需要保證查詢到位置的左邊所有元素都滿足小於等於 target，右邊所有元素都滿足大於 target。

當出現 a[mid] > target 時，說明我們要查詢的位置一定在 [left, mid - 1] 範圍內，當然也可以寫成 [left, mid) ；當出現 a[mid] <= target 時，說明要查詢的位置有可能是當前的 mid，也有可能是當前 mid 右邊的某個位置，所以此時要查詢的位置一定在 [mid, right] 範圍內。

因此，當 a[mid] > target，將 right = mid - 1 ；當 a[mid] <= target，將 left = mid。
當最後 left == right 即兩個指標相遇時退出迴圈，最後要判斷一下相遇位置處的元素是否等於目標值 target。如果等於目標值，就返回 left 或者 right，如果不等於目標值，說明不存在該元素，那麼就返回 -1 。

但是要注意的是，在這裡取 mid 時，我們不能和之前一樣取 (left + right) >> 1，而要採取 (left + right + 1) >> 1 的形式。我們可以假設只有陣列兩個元素，兩個元素都等於目標值，顯然此時我們要找的最後一個位置為下標1。我們模擬一下，初始情況下 left 為 0，right 為 1，如果採用 (left + right) >> 1，那麼此時的 mid 就等於 0，這個時候出現了 left 依舊等於之前 left 的情況，那麼顯然這個時候區間無法進行縮小，left 會一直等於 0，這個時候就陷入死迴圈了。

我們仔細看一下，當前這種情況的特點是 left + 1 == right，那麼我們取 mid 時:
mid = (left + right) >> 1 = (2 * left + 1) >> 1 = left，很明顯left 會一直等於 mid。
如果我們能夠讓 left 在這種 left + 1 == right 情況下使得 left 取到 right 即往後一位，那麼我們的區間範圍就得以縮小，也不會陷入死迴圈。所以我們採用 (left + right + 1) >> 1 取 mid，問題就得以解決了。此時：
mid = (left + right + 1) >> 1 = (2 * left + 2) >> 1 = left + 1 = right，可以看出 left 往後了一位。

歸根究底還是因為整形資料除 2 會自動進行向下取整的問題，進行 +1 操作後向上取整就可以解決這個問題。

查詢等於目標值終止位置圖解（取mid向上取整）

（1）

（2）

（3）

（4）

查詢等於目標值終止位置圖解（取mid向下取整）*

（1）

（2）

（3）

（4）

查詢等於目標值終止位置程式碼

int BinarySearchlast(vector<int> &v, int target){
    int left = 0, right = v.size() - 1;
    while(left < right){
        int mid = (left + right + 1) >> 1;
        if(v[mid] > target)
            right = mid - 1;
        else
            left = mid;
    }
    return v[left] == target ? left : -1;
}

---

相關試題及完整程式

相關試題

Acwing 789.數的範圍
Leetcode 34.在排序陣列中查詢元素的第一個和最後一個位置

完整程式

#include<iostream>
#include<vector>
using namespace std;

//二分查詢
int BinarySearch(vector<int> &v, int target){
    int left = 0, right = v.size() - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(v[mid] == target)
            return mid;
        if(v[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

//二分查詢法遞迴寫法
int BinarySearchRec(vector<int> &a, int left, int right, int target) {
    int mid = (left + right) >> 1;
    if(left <= right){
        if(a[mid] == target)
            return mid;
        if(a[mid] < target)
            return BinarySearchRec(a, mid + 1, right, target);
        else
            return BinarySearchRec(a, left, mid - 1, target);
    }
    return -1;
}

//查詢元素起始位置
int BinarySearchfirst(vector<int> &v, int target){
    int left = 0, right = v.size() - 1;
    while(left < right){
        int mid = (left + right) >> 1;
        if(v[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return v[left] == target ? left : -1;
}

//查詢元素終止位置
int BinarySearchlast(vector<int> &v, int target){
    int left = 0, right = v.size() - 1;
    while(left < right){
        int mid = (left + right + 1) >> 1;
        if(v[mid] > target)
            right = mid - 1;
        else
            left = mid;
    }
    return v[left] == target ? left : -1;
}

int main(){
    vector<int> v = {7,7,7,7};
    cout<<BinarySearchFirst(v, 7)<<endl;
    cout<<BinarySearchLast(v, 7)<<endl;
    cout<<BinarySearchRec(v, 0, v.size() - 1, 7)<<endl;
    cout<<BinarySearch(v, 7)<<endl;
}