二分查找

描述

在有序的数组里找出指定的值，返回该值在数组中的索引。

非递归实现

var arr = [ 0, 3, 4, 6, 9, 11, 12, 46, 48, 50, 66, 71, 100 ];
var binarySearch = function(seq, target) {
  var start = 0;
  var end = seq.length - 1;
  var pos = -1;
  var val;
  while(start <= end) {
    pos = Math.floor((start + end) / 2);
    val = seq[pos];
    if (val > target) {
      end = pos - 1;
    } else if (val < target) {
      start = pos + 1;
    } else {
      break;
    }
  }
  return start > end ? -1 : pos;
};
var index = binarySearch(arr, 11);
console.log(index);

递归实现

var arr = [ 0, 11, 12, 46, 48, 50, 66, 71, 100 ];
var binarySearch = function(seq, target, start, end) {
  if (start > end) {
    return -1;
  }
  var pos = Math.floor((start + end) / 2);
  var val = seq[pos];
  if (val > target) {
    return binarySearch(seq, target, start, pos - 1);
  }
  if (val < target) {
    return binarySearch(seq, target, pos + 1, end);
  }
  if (val === target) {
    return pos;
  }
}
var index = binarySearch(arr, 0, 0, arr.length - 1);
console.log(index);