二分算法实战：查找有序数组中元素的首尾位置

前言

当解空间具有'二段性'时，二分法往往是突破口。核心思路是根据区间中点判断答案落在哪一侧，然后舍弃一半区间继续查找。时间复杂度通常为 O(logN)。

STL 提供了现成工具：lower_bound 返回大于等于 x 的最小元素迭代器，upper_bound 返回大于 x 的最小元素迭代器，两者均为 O(log N)。理解底层逻辑比单纯调用 API 更重要。

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

题目描述

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

原理分析

标准二分只能找到任意一个匹配项。要确定范围，需要分别寻找左边界和右边界。

1. 定义左右指针：指向数组头尾。
2. 二分区间收缩：根据中点值与目标值的关系移动指针。
3. 验证端点合法性：防止越界或找不到目标值。

注意死循环陷阱：区间缩小条件及 mid 取整方式。查找左边界时通常向下取整，查找右边界时通常向上取整，避免 left = mid 导致无法收敛。

代码实现

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 \le a[i] \le y$。

原理分析

这本质上是区间计数问题。只要找到第一个大于等于 x 的位置（左端点）和最后一个小于等于 y 的位置（右端点），数量即为 right - left + 1。若找到的端点不合法（如左端点值大于 y 或右端点值小于 x），则说明区间内无元素。

代码实现

#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) / 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 + 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;
        int ret = binary_search(x, y);
        cout << ret << endl;
    }
    return 0;
}

总结

二分查找的核心在于把握'二段性'。无论是找单个值还是区间范围，关键在于如何定义收缩规则以避免死循环。多练习不同场景下的模板变体，能显著提升解题效率。