二分算法实战：查找元素范围与区间计数

二分算法基础

当问题的解空间具有'二段性'时，二分查找是高效的选择。核心思路是根据中点值判断目标位于哪一侧，从而舍弃一半区间。时间复杂度通常为 O(logN)。

STL 提供了便捷的二分工具：lower_bound 返回大于等于 x 的最小元素迭代器，upper_bound 返回大于 x 的最小元素迭代器，两者均为 O(log N)。理解底层原理有助于处理更复杂的边界情况。

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

题目描述

给定一个按照升序排列的整数数组 nums 和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果不存在，返回 [-1, -1]。

解题思路

我们需要分别找到左边界和右边界。

1. 找左边界：寻找第一个大于等于 target 的位置。若该位置的值不等于 target，说明不存在。
2. 找右边界：寻找最后一个小于等于 target 的位置。
3. 注意细节：计算中点时需防止溢出，且左右边界的收缩逻辑不同，避免死循环。

代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        
        // 二分查找左端点
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2; // 防止溢出写法
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        
        if (nums[left] != target) return {-1, -1};
        int retLeft = left;
        
        // 二分查找右端点
        left = 0; right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2; // 向上取整，防止死循环
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        
        return {retLeft, right};
    }
};

牛可乐和魔法封印

题目描述

给定 n 个有序数，进行 q 次查询，每次询问区间 [x, y] 内有多少个数。

解题思路

这本质上是求满足条件的数的个数。利用二分查找找到第一个大于等于 x 的位置（左端点）和最后一个小于等于 y 的位置（右端点）。若区间合法，则数量为 右端点 - 左端点 + 1。需注意判断端点是否越界或不符合条件。

代码实现

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
LL a[N];
int n;

int binary_search(int x, int y) {
    LL l = 1, r = n;
    
    // 查找左端点
    while (l < r) {
        LL mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    LL retL = l;
    if (a[l] < x) return 0; // 判断合法性
    
    // 查找右端点
    l = 1; r = n;
    while (l < r) {
        LL mid = l + (r - l + 1) / 2;
        if (a[mid] <= y) l = mid;
        else r = mid - 1;
    }
    if (a[r] > y) return 0; // 判断合法性
    
    return r - retL + 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << binary_search(x, y) << endl;
    }
    return 0;
}

总结

二分查找的核心在于维护区间的单调性。编写时务必注意 mid 的计算方式（向下取整还是向上取整）以及边界收缩条件，这是避免死循环的关键。实际应用中，先理清'找谁'（左边界还是右边界），再套用模板，最后校验结果即可。