[34] 在排序数组中查找元素的第一个和最后一个位置

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

这道题可以说是二分算法里面的集大成的题目了，建议重点复习。

要求分别查询符合条件的左侧边界与右侧边界，那么就要搞清楚二分判断后缩小哪一侧的边界。

1. 如果是求左侧边界，那么当 中数 >= 目标 时，缩右侧指针，< 时缩左侧指针。
2. 相反的，若是求右侧边界，那么当中数 <= 目标时，缩左侧，> 时缩右侧边界。

最后还需要排除目标数在数组中不存在的问题，这个只需要判断结果是否越界或合法即可。

function searchRange(nums: number[], target: number): number[] {
  const res: number[] = [-1, -1];
  if (nums.length === 0) return res;

  // 求左边界
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  if (left < nums.length && nums[left] === target) {
    res[0] = left;
  } else {
    res[0] = -1;
  }

  // 求右边界
  left = 0;
  right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  if (right >= 0 && nums[right] === target) {
    res[1] = right;
  } else {
    res[1] = -1;
  }

  return res;
}