[!info] related notes 算法面试题型 MOC 二分查找

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

题目

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

思路

• 先用 lowerBound(target) 找到第一个 >= target 的位置 L
• 再用 upperBound(target) 找到第一个 > target 的位置 R（目标右边界的下一个位置）
• 如果 L == n 或 nums[L] != target，说明不存在
• 否则答案是 [L, R - 1]

代码（JavaScript）

function lowerBound(nums, target) {
  let l = 0, r = nums.length; // [l, r)
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

function upperBound(nums, target) {
  let l = 0, r = nums.length; // [l, r)
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] > target) r = mid;
    else l = mid + 1;
  }
  return l;
}

var searchRange = function(nums, target) {
  const L = lowerBound(nums, target);
  if (L === nums.length || nums[L] !== target) return [-1, -1];
  const R = upperBound(nums, target);
  return [L, R - 1];
};