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

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

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

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？  

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2：

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3：

输入：nums = [], target = 0 输出：[-1,-1]  

提示：

0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组 -109 <= target <= 109

var searchRange = function(nums, target) {
  let start = -1, end = -1
  if (nums.length === 0) {
    return [start, end]
  }
  let l = 0, r = nums.length - 1
  while(l !== undefined || r !== undefined) {
    if (l !== undefined) {
      if (nums[l] < target) {
        l++
      } else if (nums[l] > target) {
        break
      } else {
        start = l
        l = undefined
      }
    }
    if (r !== undefined) {
      if (nums[r] > target) {
        r--
      } else if (nums[r] < target) {
        break
      } else {
        end = r
        r = undefined
      }
    }
  }
  return [start, end]
};

解题思路： 没有完成进阶能力的要求，算是简单的解除题目了，双指针同时向中心逼近的思路。后面看了题解，想要达到logn级别的时间复杂度可以用二分法，自己用二分法再实现一次

var searchRange = function(nums, target) {
  let start = -1, end = -1
  const len = nums.length
  let l = 0, r = len - 1 
  let index = -1
  while(l <= r) {
    let mid = (l + r) >> 1
    if (nums[mid] < target) {
      l = mid + 1
    } else if (nums[mid] > target) {
      r = mid - 1
    } else if (nums[mid] === target) {
      index = mid
      break
    }
  }
  if (index === -1) {
    return [start, end]
  } else {
    let j = index, k = index
    while(j >= 0) {
      if (nums[j] !== nums[j - 1]) {
        start = j
        break
      }
      j--
    }
    while(k < len) {
      if (nums[k] !== nums[k + 1]) {
        end = k
        break
      }
      k++
    }
    return [start, end]
  }
};