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;
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注