二分查找的前提为:数组、有序。逻辑为:优先和数组的中间元素比较,如果等于中间元素,则直接返回。如果不等于则取半继续查找。
arr[mid]){
return binarySearch(target,mid+1,end);
}else{
return binarySearch(target,mid-1);
}
return -1;
}
/**
* 有序的二分查找,返回-1或存在的数组下标。不使用递归实现。
* @param target
* @param arr
* @returns {*}
*/
function binarySearch(target,arr) {
var start = 0;
var end = arr.length-1;
while (start<=end){
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
start = mid+1;
}else{
end = mid-1;
}
}
return -1;
}
写完有序,自然而然的想到了无序的情况如何使用二分查找呢?马上想到先使用快排分组,分好组再二分。代码如下:
0){
//使用快速排序。以mid为中心划分大小,左边小,右边大。
var left = [];
var right = [];
//选择第一个元素作为基准元素(基准元素可以为任意一个元素)
var pivot = arr[0];
//由于取了第一个元素,所以从第二个元素开始循环
for(var i=1;ipivot ? right.push(item) : left.push(item);
}
//得到经过排序的新数组
if(target==pivot){
return true;
}else if(target>pivot){
arr = right;
}else{
arr = left;
}
}
return false;
}
写完用快速排序实现的无序二分查找,仔细想了一下该算法的时间复杂度,发现还不如直接一个for循环来得快
以上所述是小编给大家介绍的JavaScript实现二分查找实例代码。编程之家 jb51.cc 收集整理的教程希望能对你有所帮助,如果觉得编程之家不错,可分享给好友!感谢支持。