使用js实现二分查找

二分查找，也称为折半查找，是指在有序的数组里找出指定的值，返回该值在数组中的索引。

查找步骤如下：

从有序数组的最中间元素开始查找，如果该元素正好是指定查找的值，则查找过程结束。否则进行下一步;
如果指定要查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作;
重复以上过程，直到找到目标元素的索引，查找成功;或者直到子数组为空，查找失败。

优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

实现方式

非递归

//arr:数组;key:查找的元素
function search(arr, key) {
  //初始索引开始位置和结束位置
  var start = 0,
    end = arr.length - 1;
  while (start <= end) {
    //取上限和下限中间的索引
    var mid = parseInt((end + start) / 2);
    if (key == arr[mid]) {
      //如果找到则直接返回
      return mid;
    } else if (key > arr[mid]) {
      //如果key是大于数组中间索引的值则将索引开始位置设置为中间索引+1
      start = mid + 1;
    } else {
      //如果key是小于数组中间索引的值则将索引结束位置设置为中间索引-1
      end = mid - 1;
    }
  }
  //如果在循环内没有找到查找的key(start<=end)的情况则返回-1
  return -1;
}
var arr = [0, 13, 21, 35, 46, 52, 68, 77, 89, 94];
search(arr, 68); //6
search(arr, 1); //-1

递归

//arr:数组;key:查找的元素;start:开始索引;end:结束索引
function search2(arr, key, start, end) {
  //首先判断当前起始索引是否大于结束索引,如果大于说明没有找到元素返回-1
  if (start > end) {
    return -1;
  }
  //如果手动调用不写start和end参数会当做第一次运行默认值
  //三元表达式:如果不写end参数则为undefined说明第一次调用所以结束索引为arr.length-1
  //如果是递归调用则使用传进来的参数end值
  var end = end === undefined ? arr.length - 1 : end;
  //如果 || 前面的为真则赋值start,如果为假则赋值后面的0
  //所以end变量没有写var end = end || arr.length-1;这样如果递归调用时候传参end为0时会被转化为false,导致赋值给arr.length-1造成无限循环溢出;
  var start = start || 0;
  //取中间的索引
  var mid = parseInt((start + end) / 2);
  if (key == arr[mid]) {
    //如果找到则直接返回
    return mid;
  } else if (key < arr[mid]) {
    //如果key小于则递归调用自身,将结束索引设置为中间索引-1
    return search2(arr, key, start, mid - 1);
  } else {
    //如果key大于则递归调用自身,将起始索引设置为中间索引+1
    return search2(arr, key, mid + 1, end);
  }
}
var arr = [0, 13, 21, 35, 46, 52, 68, 77, 89, 94];
search2(arr, 77); //7
search2(arr, 99); //-1