Leetcode34在排序數(shù)組中查找元素的第一個和最后一個位置(二分法求解)

給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 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

然后再根據(jù)按照找到的target去向左向右延伸，找到符合要求的開始和結(jié)束位置

因為簡單二分法中正常沒有重復(fù)且存在一個mid的情況下，我們只需要return對應(yīng)的mid就行了，但這道題可能有零個或者多個，所以選擇多加一個標(biāo)識來判斷循環(huán)完事之后，是否有這樣一個中間位置滿足條件。