二分查找有序数值列表

findIndex.ts

/**
 * 二分查找有序数值列表
 * [1, 4, 10, 300, 5000000]
 *
 * Benchmark 结果，
 *
 * [1, 4, 10, 300, 5000000].findIndex((el) => el === 500);
 * 原生 x 95,827,672 ops/sec ±0.87% (88 runs sampled)
 *
 * findIndex(500, [1, 4, 10, 300, 5000000]);
 * 自制 x 87,703,716 ops/sec ±0.28% (84 runs sampled)
 *
 * TODO:
 * - 上述 Benchmark 用例使用的数据较小，可使用较大数据集测试；
 * - 实现 "用条件判断减少一次循环" 并测试
 * - 如果数据集的体量会影响效率，就提供一个 "是否大数据集" 选项，用来切换
 * - 统一上测试报告
 */

type FI<T> = {
  (target: T, collection: T[]): T
};

type FIN = FI<number>;

const findIndex:FIN = (target, collection) => {
  let lowIdx = 0;
  let highIdx = collection.length - 1;

  let midIndex: number;
  let guess: number;

  while (lowIdx <= highIdx) {
    midIndex = Math.floor((lowIdx + highIdx) / 2);
    guess = collection[midIndex];

    if (guess === target) {
      return midIndex;
    }

    if (guess < target) {
      lowIdx = midIndex + 1;

      /* 这么操作就是少了次循环，但不确定能否提升效益
      if (lowIdx === highIdx) {
        if (collection[lowIdx] === target) {
          return lowIdx;
        } else {
          return -1;
        }
      }
      */
    }

    if (guess > target) {
      highIdx = midIndex - 1;

      // TODO: 同上
    }
  }

  return -1;
}

const result = findIndex(500, [1, 4, 10, 300, 5000000]);
console.log(result);