Binary Search

[barretlee]

#25 中提到的顺序查找，是通过 key 遍历查找链表拿到对应的 value，其插入动作也是一个查询的过程——找到了 key 就重置 value，否则在链表最前方插入节点。构建这种无序的链表，成本很低，但由于其数据结构的熵比较大，做大量操作时成本偏高，尤其是链表很长的时候。

二分查找（Binary Search），就需要我们在构建符号表的时候将数据结构规范化。通过一个数组来储存数据的 keys，然后在对应的另一个数组中储存 vals，通过下表将 key 和 val 意义对应起来。

而在构建符号表的时候，可以通过二分法就行处理，如：

/chapters/chapter-3-searching/3.1-elementary-symbol-tables/binarySearchST.js

function binarylSearchST() {
  var keys = [], vals = [];
  return {
    keys: keys,
    vals: vals,
    put: function(key, val) {
      var pos = this.rank(key);
      var N = keys.length;
      if(pos == 0) {
        keys[0] = key;
        vals[0] = val;
      }
      if(pos < N && keys[pos] === key) {
        vals[pos] = val;
        return;
      }
      for(var i = N; i >= pos + 1; i--) {
        keys[i + 1] = keys[i];
        vals[i + 1] = vals[i];
      }
      keys[i] = key;
      vals[i] = val;
    },
    get: function(key) {
      var pos = this.rank(key);
      if(pos >= 0) {
        return {
          key: keys[pos],
          val: vals[pos]
        }
      }
      return -1;
    },
    rank: function(key) {
      var start = 0, end = Math.max(keys.length - 1, 0), mid;
      while(start < end) {
        mid = ((end - start) >> 1) + start;
        if(!keys[mid]) return mid;
        if(keys[mid] < key) end = mid - 1;
        else if (keys[mid] > key) start = mid + 1;
        return mid;
      }
      return start;
    }
  }
}

使用 rank 方法，让我们在构建和查询符号表的时候，效率都特别高。在一个长度为 N 的有序数组中进行二分查找最多需要 lgN + 1 次比较，然而插入效率却有点低，一次插入最坏的效果是需要 ~2N 次访问数组，也就是说构建一个长度为 N 的符号表需要 ~N² 次访问，效率比 #25 更低。