C++ 二分查找算法模板及例题详解

// 左边界
int l = 0, r = n - 1;
int begin = -1;
while(l <= r) {
    int mid = (r - l) / 2 + l;
    if(check1(mid)){
        r = mid - 1;
        begin = mid;
    } else l = mid + 1;
}

// 右边界
l = 0, r = n - 1;
int end = -1;
while(l <= r){
    int mid = (r - l) / 2 + l;
    if(check2(mid)){
        l = mid + 1;
        end = mid;
    } else r = mid - 1;
}

if(!check(begin)) begin = -1;
if(!check(end)) end = -1;
return {begin, end};

例题

1. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (r - l + 1) / 2 + l;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }
};

2. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return { -1,-1 };
        int begin = 0, end = 0;
        
        // 1. 二分左端点
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = ((r - l) >> 1) + l;
            if (nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        if (nums[l] != target) return { -1,-1 };
        else begin = l;
        
        // 2. 二分右端点
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = ((r - l + 1) >> 1) + l;
            if (nums[mid] > target) r = mid - 1;
            else l = mid;
        }
        return { begin, r };
    }
};

使用优化模板实现如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return { -1,-1 };
        int begin = -1, end = -1;
        
        // 1. 二分左端点
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] >= target){
                r = mid - 1;
                begin = mid;
            } else l = mid + 1;
        }
        
        // 2. 二分右端点
        l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] <= target) {
                l = mid + 1;
                end = mid;
            } else r = mid - 1;
        }
        
        if(nums[begin] != target) begin = -1;
        if(nums[end] != target) end = -1;
        return { begin, end };
    }
};

3. x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        if (x < 1) return 0;
        int l = 1, r = x;
        while (l < r) {
            long long mid = (r - l + 1) / 2 + l; // 防止溢出
            if (mid * mid <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

4. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

5. 山脉数组的峰顶索引

思路：该题仍具有二段性，左边递增，右边递减。封顶的左边区间一定是递增的，套用模板三找最右端点。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l = 1, r = arr.size() - 2;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (arr[mid] > arr[mid - 1]) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};

6. 寻找峰值

思路：该题有多个峰值存在，在两个封顶之间的区间内，从左到右一定递增，故套用模板二，找区间左端点即可。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

7. 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        int x = nums[r];
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] <= x) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

8. 点名

思路：按照缺失的数分为左右两个区间。左边 nums[i] == i，右边 nums[i] > i。当缺失的数是最后一个数时，需特殊判断，因此 r 从 n 开始。

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int l = 0, r = records.size();
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (records[mid] == mid) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

9. A-B 数对

思路：依次枚举 A，将问题转变成统计数列中 B+C 出现了多少次。先对数列排序，找到连续段的左端点和右端点。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main() {
    int n, c;
    cin >> n >> c;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int tot = 0;
    for (int i = 0; i < n; i++)
        tot += upper_bound(a, a + n, a[i] + c) - lower_bound(a, a + n, a[i] + c);
    cout << tot << endl;
    return 0;
}

10. 进击的奶牛

思路：构造判断条件，存在一个分界线 ans，当 x 大于 ans 时就没有合法的安置方案，当 x 小于或等于 ans 时，则一定存在一个合法的安置方案。

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005], n, m;
bool check(int mid) {
    int now = 0, cnt = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] - a[now] >= mid)
            cnt++, now = i;
    }
    return cnt + 1 >= m;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int l = 1, r = a[n - 1] - a[0];
    while (l < r) {
        int mid = (r - l + 1) / 2 + l;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}