每日算法 - JavaScript解析：在排序数组中查找元素的第一个和最后一个位置

• 一、任务描述：
• • > 示例 1
  • > 示例 2
  • > 示例 3
• 二、题意解析
• 三、解决方案：
• 往期内容 💨

一、任务描述：

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

注意：

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

本题取自 leetcode 算法基础中级

> 示例 1

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

> 示例 2

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

> 示例 3

输入：nums = [], target = 0
输出：[-1,-1]

二、题意解析

根据题目，可以得出：

• nums 非递减数组， 只可能出现 -109 ~ target【N个target】 ~ 109 这样子的数，我们需要求出第一个target 和 最后一个target 出现的下标。
• 需要写出时间复杂度为 O(log n) 的解题方案

解题思路①
根据Array构造函数自带的 nums.indexOf(target) 和 nums.lastIndexOf(target) 求出下标，这两个函数的时间复杂度为 O（nlogn）或 O（n）（根据不同浏览器，算法不同）。 数据量少的时候，差别不大。

解题思路②
根据题目中提及的 nums 为非递减数组，非递减数组：对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

根据二分查找的定义可以知道，它满足了使用二分查找的条件，所以，我们可以使用二分进行查找下标。

注：但是由于本文是寻找开始和结束的下标，所以需要更改一下二分查找到匹配值后的操作。具体看代码及对应注释！

三、解决方案：

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var searchRange = function(nums, target) {// return [nums.indexOf(target), nums.lastIndexOf(target)]const getIndex = (nums, target, isLeft = false) => {let left = 0, right = nums.length - 1while(left <= right) {const mid = Math.floor((right + left) / 2)const curVal = nums[mid]if(curVal > target) right = mid - 1else if(curVal < target) left = mid + 1else {if(isLeft) {// 当要取最左边的值，也就是开始的下标。当匹配到target的时候，判断其左边还有没有匹配的值。// 如有，则将右边查找的范围下标缩小 至 当前可知的最左边下标，也就是 mid - 1。// 反之，则证明当前mid是最左边的值下标，直接输出mid。if(curVal == nums[mid - 1]) {right = mid - 1} else {return mid}} else {// 当要取最右边的值，也就是结束的下标。当匹配到target的时候，判断其右边还有没有匹配的值。// 如有，则将左边查找的范围下标缩小 至 当前可知的最右边下标，也就是 mid + 1。// 反之，则证明当前mid是最右边的值下标，直接输出mid。if(curVal == nums[mid + 1]) {left = mid + 1} else {return mid}}}}// 匹配不到则返回 -1return -1}return [getIndex(nums, target, true), getIndex(nums, target)]
};

往期内容 💨

🔥 ＜开源： 推荐10个开源的前端低代码项目＞

🔥 ＜ CSS小技巧：那些不常用，却很惊艳的CSS属性 ＞

🔥 ＜ 开源项目框架：推荐几个开箱即用的开源管理系统 - 让开发不再复杂 ＞

🔥 ＜ JavaScript技术分享： 大文件切片上传 及 断点续传思路 ＞

🔥 ＜ 每日技巧： JavaScript代码优化 ＞