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

题目描述:## 题目描述:

难度：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
  }
};