前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode34在排序数组中查找元素的第一个和最后一个位置(二分法求解)

Leetcode34在排序数组中查找元素的第一个和最后一个位置(二分法求解)

原创
作者头像
伯约同学
发布2022-03-19 20:53:43
2390
发布2022-03-19 20:53:43
举报
文章被收录于专栏:javascript学习笔记

Leetcode34在排序数组中查找元素的第一个和最后一个位置(二分法求解)

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

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

答题:

代码语言:javascript
复制
/**
 \* @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 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档