由二分搜索算法引发的代码优化思考

[Hugo-seth]

代码地址：https://github.com/Hugo-seth/exercises/blob/master/binary-search/index.js

最近在做 JS 的代码练习，昨天要实现的是“二分搜索”算法，点击这里查看要求。

这个算法其实不难，我们只要知道数组的 sort 方法是如何比较大小的就能很快的实现：

function binarySearch(arr, item) {
  let result;

  (function _search(_arr) {
    if (_arr.length > 0) {
      let midIndex = Math.floor(_arr.length / 2)

      let _result = _compare(_arr[midIndex], item)
      if (_result === 0) {
        result = arr.indexOf(item)
      } else if (_result > 0) {
        _search(_arr.slice(0, midIndex))
      } else {
        _search(_arr.slice(midIndex + 1))
      }
    } else {
      result = -1
    }
  })(arr)

  return result
}

function _compare(a, b) {
  let _a = String(a),
    _b = String(b),
    _a_len = _a.length,
    _b_len = _b.length,
    length = Math.min(_a_len, _b_len)

  for (let i = 0; i < length; i++) {
    let _a_code = _a.charCodeAt(i),
      _b_code = _b.charCodeAt(i)

    if (_a_code > _b_code) {
      return 1
    } else if (_a_code < _b_code) {
      return -1
    }
  }

  if (_a_len > _b_len) {
    return 1
  } else if (_a_len < _b_len) {
    return -1
  } else {
    return 0
  }
}

module.exports = binarySearch

上面的难点是 _compare 函数的实现，先将比较的两数转换成 String，再比较每一位的 charCode 。

我们再仔细看 _search 函数的代码，如果找到的话：result = arr.indexOf(item)，我们想一下如果可以用 indexOf 方法的话哪还需要自己写什么“二分搜索”，这不就是个伪命题╮(╯▽╰)╭

所以我们改一下 binarySearch 函数：

function binarySearch(arr, item) {
  let result, startIndex = 0;

  (function _search(arr, item) {
    if (arr.length > 0) {
      let midIndex = Math.floor(arr.length / 2)

      let _result = _compare(arr[midIndex], item)
      if (_result === 0) {
        result = startIndex + midIndex
      } else if (_result > 0) {
        _search(arr.slice(0, midIndex), item)
      } else {
        startIndex += (midIndex + 1)
        _search(arr.slice(midIndex + 1), item)
      }
    } else {
      result = -1
    }
  })(arr, item)

  return result
}

我们新增了一个变量来保存每次查找时的开始序号，在递归时更新它，最后根据它得出结果。这下看起来好像没问题了，我们运行一下测试命令：npm test

还有一条没通过，最后一项测试竟然触发了 5000 次数组项的查找！

刚看到这个，我是没懂为什么会触发了这么多次的查找。仔细 debugger 了之后，发现是数组的 slice 方法会触发数组项的 get 。但这好像是无法解决的问题。所以我提交的时候还写了如下注释：

事实证明还是太年轻，晚上睡觉的时候突然想到为什么要传数组进去，内存开销也挺大的，直接传开始序号和结束序号进去不就行了，这样就只会在调用_compare 方法的时候才触发一次 get 。修改代码如下：

function binarySearch(arr, item) {
  let result,
    startIndex = 0,
    endIndex = arr.length - 1;

  (function _search(startIndex, endIndex) {
    if (endIndex - startIndex >= 0) {
      let midIndex = Math.floor((startIndex + endIndex) / 2)

      let _result = _compare(arr[midIndex], item)
      if (_result === 0) {
        result = midIndex
      } else if (_result > 0) {
        endIndex = midIndex - 1
        _search(startIndex, endIndex)
      } else {
        startIndex = midIndex + 1
        _search(startIndex, endIndex)
      }
    } else {
      result = -1
    }
  })(startIndex, endIndex)

  return result
}

终于，我们完成的算法可以通过所有的测试了。

总结

第一个版本的代码考虑不足，用了不能用的方法。第二个版本只是最后一项测试通不过，而实际使用的话是不会有问题的。但却有值得优化的地方：

1. 每次都传入一个新数组，内存的开销不小

2. 每次通过 slice 方法生成新数组的时候都要访问新数组的项。虽然浏览器会替我们优化：只在第一次 slice 的时候访问了新数组的所有项，后续的 slice 应该是用的缓存所以没有访问。

第三个版本解决了上面两个问题：不再传入数组，而是每次传入两个 Number ，并且不再需要使用 slice 方法。