二分查找詳解

• 2021 年 12 月 16 日
• 筆記

將二分查找問題分為兩種情況討論，一種是有序序列中不存在重複元組，另一種是有序序列中存在重複元素

一、不存在重複元素

分為三種情況討論，>=（大於或者等於）、>（大於）和<=（小於或者等於）
有序序列為{1, 3, 4, 5, 7, 8, 9, 10, 12}

大於或者等於target

可以用lower_bound函數代替
程式碼如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a = {1, 3, 4, 5, 7, 8, 9, 10, 12};
    int n = (int)a.size();
    int target;
    function<int(int)> found = [&](int target){
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(a[mid] == target){
                return mid;
            }else if(a[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    };
    while(cin >> target){
        cout << found(target) << endl;
    }
    return 0;
}

注意以下幾點：

1. 當a[mid]等於target時，直接返回mid;
2. 當a[mid]小於target時，left = mid + 1;
3. 當a[mid]大於target時，right = mid;
4. 循環條件是left < right，否則會出現死循環的情況。

大於target

可以用upper_bound函數代替
程式碼如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a = {1, 3, 4, 5, 7, 8, 9, 10, 12};
    int n = (int)a.size();
    int target;
    function<int(int)> found = [&](int target){
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(a[mid] <= target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    };
    while(cin >> target){
        cout << found(target) << endl;
    }
    return 0;
}

注意以下幾點：

1. 當a[mid]小於或者等於target時，left = mid + 1;
2. 當a[mid]大於target時，right = mid;
3. 循環條件是left < right，否則會出現死循環的情況。

小於或者等於target

相比於大於target的情況，只需要將返回值改為left – 1即可
程式碼如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a = {1, 3, 4, 5, 7, 8, 9, 10, 12};
    int n = (int)a.size();
    int target;
    function<int(int)> found = [&](int target){
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(a[mid] <= target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left - 1;
    };
    while(cin >> target){
        cout << found(target) << endl;
    }
    return 0;
}

二、存在重複元素

分為兩種情況討論，尋找第一個小於或者等於target的位置和第一個大於target的位置
有序序列為{1, 3, 3, 4, 5, 5, 7, 8, 9, 10, 12}

第一個大於target的位置

這種情況跟不存在重複元素下對應的情況一致，直接套用上面的程式碼即可

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a = {1, 3, 3, 4, 5, 5, 7, 8, 9, 10, 12};
    int n = (int)a.size();
    int target;
    function<int(int)> found = [&](int target){
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(a[mid] <= target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    };
    while(cin >> target){
        cout << found(target) << endl;
    }
    return 0;
}

第一個大於或者等於target的位置

程式碼如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a = {1, 3, 3, 4, 5, 5, 7, 8, 9, 10, 12};
    int n = (int)a.size();
    int target;
    function<int(int)> found = [&](int target){
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(a[mid] == target){
                if(mid == left || a[mid - 1] < target){
                    return mid;
                }else{
                    right = mid;
                }
            }else if(a[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    };
    while(cin >> target){
        cout << found(target) << endl;
    }
    return 0;
}

相比於不存在重複元素時對應的情況，需要對a[mid] == target的情況展開討論，討論情況如下：

1. 如果mid恰好是最左邊left位置的元素，那麼直接返回mid即可
2. 如果mid不是最左邊left位置的元素，但是mid左邊的第一個元素小於target，即a[mid – 1] < target，那麼也是直接返回mid即可
3. 其餘情況下，right = mid。