Leetcode34在排序数组中查找元素的第一个和最后一个位置(二分法求解)
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
答题:
/**
\* @param {number[]} nums
\* @param {number} target
\* @return {number[]}
*/
var searchRange = function(nums, target) {
let left = 0
let right = nums.length
let center = false
while(left < right){
• let mid = Math.floor(left + (right - left)/2)
• if(nums[mid] < target){
• left = mid + 1
• }else if(nums[mid] > target){
• right = mid
• }else{
• center = mid
• left = mid
• right = mid
• break
• }
}
if(center === false){
• return [-1,-1]
}else{
• while(nums[left] == target){
• left--
• }
• while(nums[right] == target){
• right++
• }
• return [left+1,right-1]
}
};
解题思路,先找到nums[mid] === target的 mid
然后再根据按照找到的target去向左向右延伸,找到符合要求的开始和结束位置
因为简单二分法中正常没有重复且存在一个mid的情况下,我们只需要return对应的mid就行了,但这道题可能有零个或者多个,所以选择多加一个标识来判断循环完事之后,是否有这样一个中间位置满足条件。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。