二分查找(BinSearch)的Javascript实现

时间:2024-09-29 11:05:26

二分查找

解析:二分查找,也为折半查找。对于一个从小到大排列的有序数组,首先要找到一个中间值,通过与中间值比较,大的放又,小的放在左边。再在两边中寻找中间值,持续以上操作,直到找到所在位置为止。

1.非递归实现

//对于一个从小到大的有序数列,返回查找值的索引(数组下标)
//二分查找,非递归方法
function BinSearch(arr, item){
var left = 0;
var right = arr.length-1;
while(left<=right){
var mid = Math.floor((left+right)/2);
if(item == arr[mid]){
return mid;
}else if(item > arr[mid]){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
var arr=[-34, 1, 3, 4, 5, 8, 34, 45, 65, 87];
console.log(BinSearch(arr,5)); //

2.递归实现

//二分查找,递归方法
function BinSearch2(arr,item,left,right){
var left = left || 0;
var right = right || arr.length-1;
var mid = Math.floor((left+right)/2);
if(item == arr[mid]){
return mid;
}else if(item > arr[mid]){
return BinSearch2(arr,item,mid+1,right);
}else{
return BinSearch2(arr,item,left,mid-1);
}
return false;
}
var arr1=[-34, 1, 3, 4, 5, 8, 34, 45, 65, 87];
console.log(BinSearch2(arr1,5)); //