如何用二分查找在有序数组中筛选指定范围的数字？

一、修复死循环问题 #

你的代码中二分查找陷入死循环的核心原因是：当start和end相邻时，mid取Math.floor((start+end)/2)会等于start，此时如果满足sortedArray[mid] < target，赋值start = mid后，start和end的关系没有变化，循环无法推进，最终卡死。

我们可以通过调整二分查找的边界定义和循环逻辑来解决这个问题，同时更精准地匹配需求：

• 左边界：找到第一个大于等于范围下限的元素索引
• 右边界：找到第一个大于范围上限的元素索引

这样利用数组的slice方法（左闭右开特性），直接截取两个边界之间的元素即可得到结果。

修正后的二分查找函数及最终实现：

// 查找第一个大于等于target的元素索引
function findFirstGreaterOrEqual(arr, target) {
  let start = 0, end = arr.length; // end初始为数组长度，兼容所有元素都小于target的情况
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] >= target) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return start;
}

// 查找第一个大于target的元素索引
function findFirstGreaterThan(arr, target) {
  let start = 0, end = arr.length;
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] > target) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return start;
}

function getNumsWithin(array, range) {
  const [lower, upper] = range;
  const leftIdx = findFirstGreaterOrEqual(array, lower);
  const rightIdx = findFirstGreaterThan(array, upper);
  return array.slice(leftIdx, rightIdx);
}

测试验证：

getNumsWithin([1,2,3,5,6,7], [3.3, 6.7]); // [5, 6]
getNumsWithin([1,2,3,5,6,7], [6, 7]); // [6, 7]
getNumsWithin([1,2,3,5,6,7], [8, 10]); // []

二、关于一次查找确定两个索引的问题 #

无法通过一次二分查找同时确定起始和结束索引。因为二分查找的核心是针对单个目标值进行边界定位，而我们需要定位的是两个独立的目标（范围下限和上限），必须通过两次独立的二分查找来分别获取左、右边界。

不过你可以将两次查找逻辑封装在同一个函数内，减少代码分散，但本质上还是两次二分过程。

内容的提问来源于stack exchange，提问作者Joji