【Leetcode每日一题】二分查找 - 在排序数组中查找元素的第一个和最后一个位置（难度⭐⭐）（18）

1. 题目解析

Leetcode链接：34. 在排序数组中查找元素的第一个和最后一个位置

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于找到给定目标值所在的数组下标区间，设计一个O(logn)的算法。

2. 算法原理

寻找左边界思路：

目标：找到数组中第一个大于或等于目标值的元素的索引。

特点：

左边区间 [left, resLeft - 1] 的所有元素都小于 target。
右边区间（包括 resLeft）[resLeft, right] 的所有元素都大于等于 target。

二分查找步骤：

初始化 left 和 right 为数组的开始和结束索引。
计算中间索引 mid（注意向下取整）。
根据 arr[mid] 与 target 的关系，调整 left 或 right 的值。
- 如果 arr[mid] < target，则更新 left = mid + 1。
- 如果 arr[mid] >= target，则更新 right = mid。
重复步骤 2 和 3，直到 left > right。
返回 left 或 right（取决于具体实现）。

注意：当 right = mid 时，应向下取整，以防止死循环。

寻找右边界思路：

目标：找到数组中最后一个大于或等于目标值的元素的索引。

特点：

左边区间 [left, resRight] 的所有元素都小于等于 target。
右边区间 [resRight + 1, right] 的所有元素都大于 target。

二分查找步骤：

初始化 left 和 right 为数组的开始和结束索引。
计算中间索引 mid（注意向上取整）。
根据 arr[mid] 与 target 的关系，调整 left 或 right 的值。
- 如果 arr[mid] <= target，则更新 left = mid。
- 如果 arr[mid] > target，则更新 right = mid - 1。
重复步骤 2 和 3，直到 left > right。
返回 right 或 left（取决于具体实现）。

注意：当 right = mid 时，应向上取整，以防止死循环。

通过合理地调整 left 和 right 的值，二分查找可以高效地找到左边界和右边界。

3. 代码编写

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, begin = -1, end = -1, mid;
        //找到区间左边界
        while(left<=right)
        {
            mid = (left + right)/2;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                begin = mid;
                right--;//right区间左移，使得mid左移，直到到达左区间边界，此时right正好和left重合
            }
        }

        left = 0, right = nums.size() - 1;

        //找到区间有边界
        while(left<=right)
        {
                        mid = (left + right)/2;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                end = mid;
                left++;//left区间右移，使得mid右移，直到到达又区间边界，此时left正好和right重合
            }
        }
        return {begin,end};
    }
};