17370845950

查找第一个等于目标值的位置时，需在找到目标后继续向左搜索。当arr[mid]==target时，记录位置并令r=mid-1；当arr[mid]target时，r=mid-1，最终返回最早出现的索引或-1。

二分查找是一种在有序数组中快速定位目标值的经典算法，时间复杂度为 O(log n)。但在实际开发中，我们常常遇到一些变体问题，比如查找第一个等于目标值的位置、最后一个等于目标值的位置，或者查找插入位置等。这些场景下标准的二分查找需要进行适当调整。

查找第一个等于目标值的位置

当数组中存在重复元素时，我们可能希望找到目标值第一次出现的索引。

关键在于：即使找到了目标值，也不能立即返回，而是要继续向左搜索。

示例代码：

function findFirstPosition(arr, target) {
  let l = 0, r = arr.length - 1;
  let result = -1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    if (arr[mid] === target) {
      result = mid;
      r = mid - 1; // 继续向左找
    } else if (arr[mid] < target) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return result;
}

查找最后一个等于目标值的位置

与上一种情况相反，我们要找的是目标值最后一次出现的位置。

核心思路是：即使找到目标值，也要继续向右搜索。

示例代码：

function findLastPosition(arr, target) {
  let l = 0, r = arr.length - 1;
  let result = -1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    if (arr[mid] === target) {
      result = mid;
      l = mid + 1; // 继续向右找
    } else if (arr[mid] < target) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return result;
}

查找插入位置（lower bound）

适用于确定目标值应插入的位置，以保持数组有序。如果目标值已存在，插入位置为其首次出现的位置前。

这在实现有序集合或去重插入时非常有用。

不需要判断是否完全相等，只需找到第一个大于等于目标值的位置。

示例代码：

function findInsertPosition(arr, target) {
  let l = 0, r = arr.length - 1;
  let result = arr.length; // 默认插在末尾
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    if (arr[mid] >= target) {
      result = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return result;
}

查找大于目标值的最小元素

有时我们需要找出第一个严格大于目标值的元素，例如在范围查询或自动补全中。

可以基于二分变形实现。

示例代码：

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

基本上就这些常见变体。掌握它们的关键是理解二分的本质：通过比较缩小搜索空间。根据具体需求调整边界移动逻辑即可。不复杂但容易忽略细节。