每天一道leetcode(Day 43)

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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是  O(log n) 级别。

如果数组中不存在目标值，返回  [-1, -1]。

示例

• 示例 1:

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

• 示例  2:

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

解题思路

因为数组是有序的，因此可以利用二分法查找到其中一个目标元素，然后从这个目标元素的位置向数组两端扩散，找到最左边的下标和最右边的下标。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  const len = nums.length;
  let start = 0,
    end = 0,
    left = 0,
    right = len - 1;
  while (left <= right) {
    const mid = (left + right) >> 1;
    if (nums[mid] === target) {
      start = end = mid;
      while (start > left && nums[start] === nums[start - 1]) start--;
      while (end < right && nums[end] === nums[end + 1]) end++;
      return [start, end];
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return [-1, -1];
};

参考

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