使用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
