JavaScript查找数组中介于两相邻元素间的数值对应索引

你当前的数组是升序有序数组，需求本质是找到最后一个小于等于number的元素索引，JavaScript提供了原生数组方法可以直接实现，不需要额外依赖第三方库。

方法1：原生findIndex实现（代码最简洁，兼容所有ES6+环境） #

findIndex会返回数组中第一个满足判定条件的元素的索引，我们只要找到第一个比number大的元素，它的前一位就是符合要求的索引：

const arr = [0, 2, 6, 10, 14, 18, 22];
const number = 13;

// 查找第一个大于number的元素位置，前一位即为目标索引
const index = arr.findIndex(item => item > number) - 1;
// 输出结果3，和预期一致

边界情况兜底 #

如果number大于数组所有元素，findIndex会返回-1，计算后会得到-2；如果number小于数组第一个元素，计算后会得到-1，可以根据业务需求加兜底逻辑：

const firstLargerPos = arr.findIndex(item => item > number);
let index;
if (firstLargerPos === -1) {
  // number大于等于数组最大值，取最后一位索引
  index = arr.length - 1;
} else if (firstLargerPos === 0) {
  // number小于数组最小值，无匹配位置，可按需赋值为-1或做其他处理
  index = -1;
} else {
  index = firstLargerPos - 1;
}

方法2：二分查找实现（大数组性能最优） #

如果需要处理长度极大的数组（万元素级以上），findIndex是线性遍历，时间复杂度为O(n)，可以用二分查找优化到O(logn)，JS没有内置二分查找方法，手写实现也很简单：

function getMatchIndex(sortedAscArr, target) {
  let left = 0;
  let right = sortedAscArr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedAscArr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  // 循环结束后right指向的就是最后一个<=target的元素索引
  return right;
}

const arr = [0, 2, 6, 10, 14, 18, 22];
const number = 13;
const index = getMatchIndex(arr, number); // 返回3

这个实现天然兼容边界情况：target比所有元素大时返回数组最后一位索引，比所有元素小时返回-1，不需要额外写兜底判断。

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