题目链接

题目描述

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

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

    示例

    示例1：

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

示例1：

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

提示

  • 0 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 是一个非递减数组

  • -10 <= target <= 10

    思路

    二分查找

    典型查找上下界问题，具体模板参考几个模板

    题解

    1. class Solution {
    2.  private:
    3.   int binarySearch(vector<int>& nums, int target, bool isLeft = true) {
    4.       int left = 0, right = nums.size();
    5.       while (left < right) {
    6.           int mid = ((right - left) >> 1) + left;
    7.           if ((isLeft && nums[mid] >= target) || nums[mid] > target) {
    8.               right = mid;
    9.           } else {
    10.               left = mid + 1;
    11.           }
    12.       }
    13.       if (isLeft) {
    14.           if (left == nums.size()) return -1;
    15.           return nums[left] == target ? left : -1;
    16.       } else {
    17.           if (left == 0) return -1;
    18.           return nums[left - 1] == target ? (left - 1) : -1;
    19.       }
    20.   }
    22.  public:
    23.   vector<int> searchRange(vector<int>& nums, int target) {
    24.       int leftBound = binarySearch(nums, target);
    25.       int rightBound = binarySearch(nums, target, false);
    26.       return vector<int>{leftBound, rightBound};
    27.   }
    28. };

    复杂度分析

  • 时间复杂度：0034-在排序数组中查找元素的第一个和最后一个位置 - 图1

  • 空间复杂度：0034-在排序数组中查找元素的第一个和最后一个位置 - 图2