题目描述:## 题目描述:
难度:Middle
相关话题:数组
、二分查找
给定一个按照升序排列的整数数组 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]
思路:
两个二分查找
的变形。
在升序排列中:
bsTail
的作用是,如果存在数字n
,找出当前数字最后一个的位置;如果不存在数字n
,找出比当前数字小的最大的数字。
bsHead
的作用是,如果存在数字n
,找出当前数字的第一个出现的位置;如果不存在,找出比当前数字大的最小的数字。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let h=bsHead(nums,target)
let t=bsTail(nums,target)
if(nums[h]===target)return [h,t]
return [-1,-1]
function bsHead(arr,n){
let lo=0,hi=arr.length-1
while(lo<hi){
let mid=Math.floor((lo+hi)/2)
if(arr[mid]<n)lo=mid+1
else hi=mid
}
return hi
}
function bsTail(arr,n){
let lo=0,hi=arr.length-1
while(lo<hi){
let mid=Math.ceil((lo+hi)/2)
if(arr[mid]>n)hi=mid-1
else lo=mid
}
return lo
}
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com