LeetCode-在排序数组中查找元素的第一个和最后一个位置「数组」

[zentan66]

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

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

进阶：

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

[zentan66]

编码

const binarySearch = (nums, target, lower) => {
  let left = 0,
    right = nums.length - 1,
    ans = nums.length
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    // 通过设置lower，查询该数的第一个索引
    if (nums[mid] > target || (lower && nums[mid] >= target)) {
      right = mid - 1
      ans = mid
    } else {
      left = mid + 1
    }
  }
  return ans
}

var searchRange = function (nums, target) {
  let ans = [-1, -1]
  const leftIdx = binarySearch(nums, target, true)
  const rightIdx = binarySearch(nums, target, false) - 1
  if (
    leftIdx <= rightIdx &&
    rightIdx < nums.length &&
    nums[leftIdx] === target &&
    nums[rightIdx] === target
  ) {
    ans = [leftIdx, rightIdx]
  }
  return ans
}

思路

其实这道题要实现并不难，但是时间复杂度有要求 所以可以通过二分查找来实现， 两个二分查找的时间复杂度是2*O(log(n))