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

二分算法核心逻辑

当问题的解具有'二段性'时，二分算法是寻找答案的高效工具。其核心思想是根据待查找区间的中点位置，分析答案会出现在哪一侧，随后舍弃一半的区间，在剩余部分继续查找。

时间复杂度通常为 O(logN)。在实际开发中，C++ STL 提供了 lower_bound（大于等于 x 的最小元素）和 upper_bound（大于 x 的最小元素），它们均返回迭代器且效率为 O(log N)，能简化边界查找过程。但理解手写二分的底层逻辑对于处理复杂边界条件至关重要。

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

问题描述

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

思路解析

我们需要分别找到目标值的左边界和右边界。这可以通过两次二分查找完成：

1. 查找左端点：寻找第一个大于等于 target 的位置。当 nums[mid] >= target 时，说明目标可能在左侧或就是 mid，因此 right = mid；否则 left = mid + 1。注意这里使用 while(left < right) 配合 mid = (left + right) / 2 向下取整，避免死循环。
2. 查找右端点：寻找最后一个小于等于 target 的位置。当 nums[mid] <= target 时，说明目标可能在右侧或就是 mid，因此 left = mid；否则 right = mid - 1。此时需使用 mid = (left + right + 1) / 2 向上取整，防止 left 无法移动导致死循环。
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 + ;
        }
        
         (nums[left] != target)  {, };
         retLeft = left;

        
        left = ; right = nums.() - ;
         (left < right) {
             mid = (left + right + ) / ;
             (nums[mid] <= target)
                left = mid;
            
                right = mid - ;
        }

         {retLeft, right};
    }
};