JavaScript搜索算法_二分查找变体-js教程-PHP中文网

JavaScript搜索算法_二分查找变体

狼影

发布： 2025-11-19 18:34:34

原创

792人浏览过

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

javascript搜索算法_二分查找变体

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

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

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

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

当 arr[mid] == target 时，记录当前位置，并将右边界 r = mid - 1，继续查找左边是否还有更早的匹配项。
当 arr[mid] < target，说明目标在右半部分，l = mid + 1。
当 arr[mid] > target，说明目标在左半部分，r = mid - 1。

示例代码：

立即学习“Java免费学习笔记（深入）”；

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;
}

登录后复制

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

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

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

当 arr[mid] == target 时，更新结果并让 l = mid + 1。
其余条件与标准二分一致。

示例代码：

立即学习“Java免费学习笔记（深入）”；

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）

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

Media.io AI Image Upscaler

Media.io推出的AI图片放大工具

查看详情

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

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

示例代码：

立即学习“Java免费学习笔记（深入）”；

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;
}

登录后复制

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

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

可以基于二分变形实现。

示例代码：

立即学习“Java免费学习笔记（深入）”；

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;
}

登录后复制

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

以上就是JavaScript搜索算法_二分查找变体的详细内容，更多请关注php中文网其它相关文章！