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

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就行了，但这道题可能有零个或者多个，所以选择多加一个标识来判断循环完事之后，是否有这样一个中间位置满足条件。