二分查找详解

• 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。