优化递归深度

binarySearch.js

function binarySearch(arr, left, right, target) {
  let mid = Math.floor((left + right) / 2);
  function getLeft() {
    return mid - 1 < left ? left : mid - 1;
  }
  function getRight() {
    return mid + 1 > right ? right : mid + 1;
  }

  if (left === right) return right; // 可以优化掉一次函数调用

  // target 在 mid 左右
  if (arr[getLeft()] < target && target < arr[getRight()]) {
    // 求距离 target 最近的点
    let val1 = target - arr[getLeft()],
      val2 = Math.abs(target - arr[mid]),
      val3 = arr[getRight()] - target;

    const indexMap = {
      [val1]: getLeft(),
      [val2]: mid,
      [val3]: getRight(),
    };
    return indexMap[Math.min(val1, val2, val3)];
  } else if (target < arr[mid]) {
    if (mid - 1 < 0) return mid; // 界外
    return binarySearch(arr, left, mid - 1, target);
  } else {
    if (mid + 1 > arr.length - 1) return mid; // 界外
    return binarySearch(arr, mid + 1, right, target);
  }
}

console.log(binarySearch([1, 3, 5, 7, 9], 0, 4, -100));