JavaScript实现二分查找实例代码
二分查找的前提为：数组、有序。逻辑为：优先和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找。
/**
*二分查找，递归实现。
*@paramtarget
*@paramarr
*@paramstart
*@paramend
*@returns{*}
*/
functionbinarySearch(target,arr,start,end){
varstart=start||0;
varend=end||arr.length-1;
varmid=parseInt(start+(end-start)/2);
if(target==arr[mid]){
returnmid;
}elseif(target>arr[mid]){
returnbinarySearch(target,arr,mid+1,end);
}else{
returnbinarySearch(target,arr,start,mid-1);
}
return-1;
}
/**
*有序的二分查找，返回-1或存在的数组下标。不使用递归实现。
*@paramtarget
*@paramarr
*@returns{*}
*/
functionbinarySearch(target,arr){
varstart=0;
varend=arr.length-1;
while(start<=end){
varmid=parseInt(start+(end-start)/2);
if(target==arr[mid]){
returnmid;
}elseif(target>arr[mid]){
start=mid+1;
}else{
end=mid-1;
}
}
return-1;
}
写完有序，自然而然的想到了无序的情况如何使用二分查找呢？马上想到先使用快排分组，分好组再二分。代码如下：
/**
*无序的二分查找。返回true/false
*@paramtarget
*@paramarr
*@returns{boolean}
*/
functionbinarySearch(target,arr){
while(arr.length>0){
//使用快速排序。以mid为中心划分大小，左边小，右边大。
varleft=[];
varright=[];
//选择第一个元素作为基准元素(基准元素可以为任意一个元素)
varpivot=arr[0];
//由于取了第一个元素，所以从第二个元素开始循环
for(vari=1;i<arr.length;i++){
varitem=arr[i];
//大于基准的放右边，小于基准的放左边
item>pivot?right.push(item):left.push(item);
}
//得到经过排序的新数组
if(target==pivot){
returntrue;
}elseif(target>pivot){
arr=right;
}else{
arr=left;
}
}
returnfalse;
}
写完用快速排序实现的无序二分查找，仔细想了一下该算法的时间复杂度，发现还不如直接一个for循环来得快
以上所述是小编给大家介绍的JavaScript实现二分查找实例代码，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！