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

题目

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

进阶：

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

示例：

  1. 输入：nums = [5,7,7,8,8,10], target = 8
  2. 输出：[3,4]
  1. 输入：nums = [5,7,7,8,8,10], target = 6
  2. 输出：[-1,-1]
  1. 输入：nums = [], target = 0
  2. 输出：[-1,-1]

解答 & 代码

题目要求 O(logn) 的时间复杂度，那么就要用到二分查找。

本题需要使用两次二分查找：

  1. 二分查找 target 的左侧边界

  2. 二分查找 target 的右侧边界

    1. class Solution {
    2. public:
    3.  vector<int> searchRange(vector<int>& nums, int target) {
    4.      // 1. 二分查找 target 的左侧边界
    5.      int left = 0;
    6.      int right = nums.size() - 1;
    7.      int leftBoundary = -1;        // target 的左侧边界
    8.      // 搜索区间为 [left, right]
    9.      while(left <= right)
    10.      {
    11.          int mid = left + (right - left) / 2;
    12.          if(nums[mid] == target)        // 如果 nums[mid] == target
    13.          {
    14.              leftBoundary = mid;        // mid 可能是左边界，因此更新 leftBoundary
    15.              right = mid - 1;        // 收缩右边界，查找是否还有更左边的元素 = target
    16.          }
    17.          else if(nums[mid] < target)
    18.              left = mid + 1;
    19.          else
    20.              right = mid - 1;
    21.      }
    23.      // 2. 二分查找 target 的右侧边界
    24.      left = 0;
    25.      right = nums.size() - 1;
    26.      int rightBoundary = -1;        // target 的右侧边界
    27.      while(left <= right)
    28.      {
    29.          int mid = left + (right - left) / 2;
    30.          if(nums[mid] == target)        // 如果 nums[mid] == target
    31.          {
    32.              rightBoundary = mid;    // mid 可能是右边界，因此更新 rightBoundary
    33.              left = mid + 1;            // 收缩左边界，查找是否还有更右边的元素 = target
    34.          }
    35.          else if(nums[mid] < target)
    36.              left = mid + 1;
    37.          else
    38.              right = mid - 1;
    39.      }
    41.      return vector<int>{leftBoundary, rightBoundary};
    42.  }
    43. };

    复杂度分析：设 nums 数组长为 N

  • 时间复杂度 O(log N)：两次二分查找
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 61.21% 的用户
  4. 内存消耗：13.3 MB, 在所有 C++ 提交中击败了 39.20% 的用户