js 实现数组查找二分法
二分法实现原理:二分查找可以解决已经排好序数组的查找问题:只要数组中包含target(即要查找的值),那么通过不断缩小包含target数组的范围,最终就可以找到它。
其算法流程如下:
开始,范围覆盖整个数组。
将数组的中间项与target进行比较,如果target比数组的中间项要小,则到数组的前半部分继续查找,反之,则到数组的后半部分继续查找。
如此,每次查找可以排除一半元素,范围缩小一半。就这样反复比较,反复缩小范围,最终就会在数组中找到target,或者确定原以为target所在的范围实际为空。
对于包含N个元素的表,整个查找过程大约要经过log(2)N次比较。
递归实现
例1:用递归二分法实现array.indexOf 功能(数组为正序排列)
function indexOf(arr,target,start,end){
start = start || 0;
end = end || arr.length - 1;
if(start > end){
return -1;
}
let mid = Math.floor((start + end)/2);
if(arr[mid] > target) {
end = mid-1;
return indexOf(arr,target,start,end);
}
else if(arr[mid] < target){
start = mid + 1;
return indexOf(arr,target,start,end);
}
else {
return mid;
}
}
let a = [0,1,2,3,4,5,6,434,435];
console.log(indexOf(a,12)); //打印结果为-1
while循环实现
function indexOf(arr,target,start,end){
start = start || 0;
end = end || arr.length - 1;
let mid = Math.floor((start + end)/2);
console.log(start,end);
while(start <= end){
console.log(start,end,target,arr[mid]);
if(target > arr[mid]){
start = mid + 1;
mid = Math.floor((start + end)/2);
}
else if(target < arr[mid]){
end = mid - 1;
mid = Math.floor((start + end)/2);
}
else {
return mid ;
}
}
console.log(start,end);
return -1;
}
let a = [0,1,2,3,4,5,6,434,435];
console.log(indexOf(a,5)); //打印结果为5