算法——二分法查找（binarySearch）
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
二分法查找的思路如下：
（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
（3）如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。
非递归算法：
-
function binarySearch(arr,key){
-
var low=
0;
//数组最小索引值
-
var high=arr.length
-1;
//数组最大索引值
-
while(low<=high){
-
var mid=
Math.floor((low+high)/
2);
-
if(key==arr[mid]){
-
return mid;
-
}
else
if(key>arr[mid]){
-
low=mid+
1;
-
}
else{
-
high=mid
-1;
-
}
-
}
-
return
-1;
//low>high的情况，这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
-
}
结果测试：
递归算法：
-
function binarySearch(arr,low,high,key){
-
if(low>high){
return
-1;}
-
var mid=
Math.floor((low+high)/
2);
-
if(key==arr[mid]){
-
return mid;
-
}
else
if(key<arr[mid]){
-
high=mid
-1;
-
return binarySearch(arr,low,high,key);
-
}
else{
-
low=mid+
1;
-
return binarySearch(arr,low,high,key);
-
}
-
}
结果测试：
