LeetCode第34题：在排列数组中查找元素的起始位置

题干

给定一个按照升序排列的整数数组 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]
复制代码

思路1：双指针

前后各一个指针，循环开始遍历，如果某指针一个指针到达target停止，知道两个都停止，则记录，退出循环。

代码实现：

执行用时：80 ms, 在所有 JavaScript 提交中击败了86.54%的用户

内存消耗：39.3 MB, 在所有 JavaScript 提交中击败了49.99%的用户

var searchRange1 = function (nums, target) {
    // 双指针
    let index = 0;
    let indey = nums.length - 1;
    while (index <= indey) {
      if (nums[index] == target && nums[indey] == target) {
        return [index, indey]
      }
      if (nums[index] != target) {
        index++
      } else if (nums[indey] != target) {
        indey--
      }
    }
    return [-1, -1]
  };
复制代码

思路2：二分查找

此题要分两个二分，分别找到重复区间的起始位置，如何找到区间的其实位置呢？

其实很简单，就是但我们如果找到了tartget值后继续二分，如果想找的是左边边界值，就将当前的max指针移动至tartget值处，如果找的是右边界值，则将min指针移动至tartget位置。

注：需要注意的是，我们在寻找有区间值时，单单将mid的值给min时不够的，因为这可能会导致min指针停留在原地，最终导致死循环，所以我们需要每次将循环时将mid的值+1

如下图分析，字迹不太公正，但可说明问题

代码实现：

执行用时：64 ms, 在所有 JavaScript 提交中击败了99.90%的用户

内存消耗：39.1 MB, 在所有 JavaScript 提交中击败了83.43%的用户

 var searchRange = function (nums, target) {
    let firstTartget = getFirstTartget(nums, target);
    let lastTarget = getlastTarget(nums, target);
    if (firstTartget == -1) {
      return [-1, -1]
    }
    return [firstTartget, lastTarget]
  };
	//寻找左区间
  function getFirstTartget(nums, target) {
    let min = 0;
    let max = nums.length - 1;
    while (min < max) {
      let mid = min + Math.floor((max - min) / 2)
      if (nums[mid] > target) {
        max = mid - 1
      } else if (nums[mid] < target) {
        min = mid + 1
      } else {
        max = mid
      }
    }
    return nums[max] == target ? max : -1
  }
	//寻找右区间
  function getlastTarget(nums, target) {
    let min = 0;
    let max = nums.length - 1;
    while (min < max) {
      let mid = min + Math.floor((max - min) / 2) + 1
      if (nums[mid] > target) {
        max = mid - 1
      } else if (nums[mid] < target) {
        min = mid + 1
      } else {
        min = mid
      }
    }
    return min
  }
  console.log(searchRange([5, 7, 7, 8, 8, 10], 6))
复制代码