javascript - js数组的二分查找性能真的比普通遍历查找性能高吗?
本文介绍了javascript - js数组的二分查找性能真的比普通遍历查找性能高吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
都说二分法查找是为了提高性能,可我在实际测试中发现所用时间要比普通遍历高不少
求教是不是代码有问题
function search(arr,dst){
var l = 0,
r=arr.length-1;
//遍历数组
while(l <= r){
var m = Math.floor((l+r)/2);//一分为二
//目标在前半段(0~m-1)
if(dst<arr[m]){r=m-1;}
//目标在后半段(m+1~r)
else if(arr[m]<dst){l=m+1;}
else{
//输出结果
//添加一个判断,确保取到的是第一个目标
if(arr[m-1]==dst){return m-1;}
return m;
}
}
//目标不在数组中
return -1;
}
var start1 = new Date()
var arr = [1, 2, 4, 6, 7, 9, 19,20, 30, 40, 45, 47,48,49,50,60,80,90,111,122,144,155,166,177,211,222,223,333,444,555,666,777];
console.log(search(arr, 777)); // 10
var end1 = new Date()
console.log(end1-start1)//20ms左右
function sear(arr,dst) {
for(var i=0;i<arr.length;i++) {
if(arr[i] == dst) {
return i;
}
}
}
var start2 = new Date()
var arr1 = [1, 2, 4, 6, 7, 9, 19,20, 30, 40, 45, 47,48,49,50,60,80,90,111,122,144,155,166,177,211,222,223,333,444,555,666,777];
console.log(sear(arr1, 777));
var end2 = new Date()
console.log(end2-start2)//不到1ms
解决方案
比较无聊,所以在chrome下的控制台里测试这个代码
function binSearch(arr,dst){
var l = 0,
r=arr.length-1;
//遍历数组
while(l <= r){
var m = (l+r)>>1;//一分为二
//目标在前半段(0~m-1)
if(dst<arr[m]){r=m-1;}
//目标在后半段(m+1~r)
else if(arr[m]<dst){l=m+1;}
else{
//输出结果
//添加一个判断,确保取到的是第一个目标
if(arr[m-1]==dst){return m-1;}
return m;
}
}
//目标不在数组中
return -1;
}
function normalSearch(arr,dst) {
for(var i=0, l=arr.length;i<l;i++) {
if(arr[i] == dst) {
return i;
}
}
}
var arr = [];
for(var i=0;i<10000;i++){
arr.push(i*3);
}
var arr2 = [1, 2, 4, 6, 7, 9, 19,20, 30, 40, 45, 47,48,49,50,60,80,90,111,122,144,155,166,177,211,222,223,333,444,555,666,777];
console.time("binary search");
for(var i=0;i<100000;i++){
binSearch(arr, 1665);
}
console.timeEnd("binary search");
console.time("normal search");
for(var i=0;i<100000;i++){
normalSearch(arr, 1665);
}
console.timeEnd("normal search");
console.time("binary search");
for(var i=0;i<100000;i++){
binSearch(arr2, 777);
}
console.timeEnd("binary search");
console.time("normal search");
for(var i=0;i<100000;i++){
normalSearch(arr2, 777);
}
console.timeEnd("normal search");
输出
binary search: 4.886962890625ms
normal search: 35.634033203125ms
binary search: 3.026123046875ms
normal search: 4.693115234375ms
现在看起来二分法的效率已经超过遍历了,所以应该是除法取整这个过程导致了二分法搜索效率的降低
这篇关于javascript - js数组的二分查找性能真的比普通遍历查找性能高吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文