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

前言

当解空间具有'二段性'时，二分法往往是突破口。核心思路是根据区间中点判断答案落在哪一侧，然后舍弃一半区间继续查找。时间复杂度通常为 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)  {, };
         retLeft = left;
        
        
        left = ; right = nums.() - ;
         (left < right) {
             mid = (left + right + ) / ; 
             (nums[mid] <= target) left = mid;
             right = mid - ;
        }
         {retLeft, right};
    }
};