[路飞]_leetcode-34-在排序数组中查找元素的第一个和最后一个位置

「这是我参与2022首次更文挑战的第27天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

给定一个按照升序排列的整数数组 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]
复制代码

提示：

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

解题思路

本题要求我们在一个升序排序后的整数数组中查找目标值 target 在数组中的区间，该区间内的数字都是 target。

很简单，我们只需要找到第一个 target 出现的位置以及最后一个 target 出现的位置即可，这两个位置就是区间的左右边界。

又因为输入数组是一个升序排序后的数组，所以我们可以利用二分查找找到第一个大于等于 target 的位置（记为 l），如果该位置的值等于 target，则继续向后查找，直到找到第一个数字不等于 target（记为 i），那么从 l 到 i-1 区间内的整数都等于 target，返回区间 [l,i-1 即可。

反之如果 l 位置的值不等于 target，则说明数组中不存在 target，返回 [-1,-1]。

而且因为本题输入数组可能为空，所以我们在开始还需要做一些特判：

1. 如果输入数组为空，则数组中肯定没有 target
2. 如果 target 小于数组中的第一个整数，则数组中肯定没有 target
3. 如果 target 大于数组中的最后一个整数，则数组中肯定没有 target

代码实现

var searchRange = function (nums, target) {
  // 特判输入数组为空或者target小于第一个数字或者target大于最后一个数字，此时数组中肯定没有target，直接返回 [-1,-1]
  if (nums.length === 0 || target < nums[0] || target > nums[nums.length - 1]) return [-1, -1]
  // 二分查找第一个大于等于 target 的位置
  let l = 0,
    r = nums.length - 1
  while (l < r) {
    const mid = (l + r) >> 1
    if (nums[mid] < target) l = mid + 1
    else r = mid
  }
  // 如果当前位置的值是 target，则继续向后查找，直到找到一个数字不等于 target
  // 此时 l~i-1区间内的数字都是 target
  if (nums[l] === target) {
    let i = l + 1
    while (nums[i] === target) i++
    return [l, i - 1]
  }
  // 如果第一个大于等于 target 的位置的值不是 target，返回 [-1,-1]
  return [-1, -1]
}
复制代码

至此我们就完成了 leetcode-34-在排序数组中查找元素的第一个和最后一个位置

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻