二分算法详解：查找元素首尾位置及区间查询

当问题的解具备二段性时，二分算法是寻找答案的高效工具。核心思路是根据中点位置判断目标落在哪一侧，随即舍弃一半区间，时间复杂度为 O(logN)。C++ STL 提供了 lower_bound（大于等于 x 的最小元素）和 upper_bound（大于 x 的最小元素），底层均基于二分实现。

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

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

算法思路 这道题需要分别找到左边界和右边界。直接遍历是 O(N)，利用有序特性可优化至 O(logN)。

1. 查找左端点：使用二分查找，当 nums[mid] >= target 时，说明目标可能在左侧或就是 mid，因此 right = mid；否则 left = mid + 1。注意循环条件是 left < right，避免死循环。
2. 查找右端点：同理，但逻辑相反。当 nums[mid] <= target 时，left = mid；否则 right = mid - 1。这里计算 mid 时需要向上取整 (left + right + 1) / 2，防止 left = mid 导致死循环。
3. 合法性校验：找到端点后，需检查该位置的元素是否真的等于 target，防止数组中无目标值的情况。

代码实现

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) / 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 + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        
        return {retLeft, right};
    }
};

牛可乐和魔法封印

题目描述 给定一个长度为 n 的升序数组 a，进行 q 次查询。每次查询给出一个区间 [x, y]，求数组中有多少个元素的值在该区间内。

算法思路 这本质上是区间计数问题。我们需要找到第一个大于等于 x 的位置（左边界）和最后一个小于等于 y 的位置（右边界）。

1. 确定范围：调用两次二分查找。第一次找左边界 l，第二次找右边界 r。
2. 边界处理：如果找到的左边界元素小于 x，或者右边界元素大于 y，说明区间内没有符合条件的数，返回 0。
3. 计算结果：若合法，结果为 r - l + 1。

代码实现

#include <iostream>
using namespace std;

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

// 查找区间 [x, y] 内的元素个数
int binary_search(int x, int y) {
    LL l = 1, r = n;
    // 查找左端点：第一个 >= x 的位置
    while (l < r) {
        LL mid = (l + r) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    LL retL = l;
    if (a[l] < x) return 0;

    // 查找右端点：最后一个 <= y 的位置
    l = 1; r = n;
    while (l < r) {
        LL mid = (l + r + 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 取整技巧以及端点合法性判断，是规避死循环误区的关键。每一道模版题的练习，都是突破瓶颈的底气。