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

查找步骤如下：

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

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

实现方式

非递归

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

递归

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