您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

力扣题:34在排序数组中查找元素的第一个和最后一个位置

题目链接:34在排序数组中查找元素的第一个和最后一个位置
题目

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

进阶:
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

思路和算法:

寻找target在数组里的左右边界,有如下三种情况:

一、target不在数组范围中,在数组左边,例如{3, 4,5},target=2;target不在数组范围中,在数组右边,例如{3, 4, 5},target=6;
二、target不在数组范围中,在数组中间,例如{3, 4, 7},target=5;
三、target在数组范围中,例如{3, 4,5},target=4。

接下来就是用二分法,分别查找左右边界,这里一开始采用了分开查找的方法,一是便于不熟练二分法的小伙伴(比如我)初次入手二分中等题,二是便于理清逻辑。
代码(C++):

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int rightborder = getRightBorder(nums, target); //返回右边界
        int leftborder = getLeftBorder(nums, target);   //返回左边界
        if (rightborder == -2 || leftborder == -2) return { -1, -1 };   //情况一
        if (rightborder - leftborder > 1) return { leftborder + 1, rightborder - 1 };   //情况三
        return { -1, -1 };  //情况二

    }
private:
    int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightborder = -2;   //用来记录rightborder是否被赋值
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            }
            else {  //当nums[mid] == target时,更新rightborder右边界
                left = mid + 1;
                rightborder = left;
            }
        }
        return rightborder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftborder = -2;   //用来记录leftborder是否被赋值
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {  //当nums[mid] == target时,更新leftborder左边界
                right = mid - 1;
                leftborder = right;
            }
            else {  
                left = mid + 1;
            }
        }
        return leftborder;
    }
};

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进