查找区间边界

如何查找有序数组中 target 的首尾位置？

• 左边界: 比较时把 nums[mid] >= target 都归入右端收窄, 结束时 left 指向最左 target;
• 右边界: 比较时把 nums[mid] <= target 都归入左端扩大, 结束时 left 指向大于 target 的第一个位置, 右边界即 left - 1;
• 两次二分共用一套左闭右开模板, 结束后都要检查答案是否真的等于 target;

为什么两次二分的判断条件不同？

• 找左边界时命中后仍要向左, 因此等号并入 right = mid 分支;
• 找右边界时命中后仍要向右, 因此等号并入 left = mid + 1 分支;

查找区间边界如何实现？

function searchRange(nums: number[], target: number): number[] {
  const res = [-1, -1];

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

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

  return res;
}

查找区间边界的复杂度是多少？

• 时间复杂度: O(log n), 两次独立二分;
• 空间复杂度: O(1);