LeetCode #34：Find First And Last Position Of Element In Sorted Array(在排序数组中查找元素的第一个和最后一个位置)

题目描述

本题是一个和二分查找相关的综合性问题，大致思路就是分别找到目标值在数组中的左边界和右边界，再返回区间即可。

问题可分为如下三种情况：

① target 在 nums 数组的最值范围之外，即 target < nums[0] || target > nums[n-1]，此时应该返回 {-1, -1}；
② target 在 nums 数组的最值范围之内，但是数组中不存在 target，此时也应该返回 {-1, -1}；
③ 数组中存在 target，此时应该返回对应的区间范围。

我们规定左（右）边界为不包含 target 的左（右）边界，代码实现如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = getLeftBorder(nums, target);
        int r = getRightBorder(nums, target);

        if(l == -2 || r == -2) // 情况1
            return {-1, -1};
        else if(r - l > 1) // 情况3，根据我们先前的定义，若nums中有target，r-l至少为2
            return {l + 1, r - 1};
        
        return {-1, -1}; // 情况2
    }

    // 寻找右边界
    int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int res = -2; // 一开始笔者把默认值设为-1，但若target的值正好为nums的最小值，默认值就和最终的区间值冲突了
        while(left <= right) {
            int mid = left + ((right - left) / 2); // 等价于(left + right) / 2，防止溢出
            if(target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
                res = left;
            }
        }

        return res;
    }

    // 寻找左边界
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int res = -2;
        while(left <= right) {
            int mid = left + ((right - left) / 2);
            if(target <= nums[mid]) {
                right = mid - 1;
                res = right;
            } else {
                left = mid + 1;
            }
        }

        return res;
    }
};