js数组的二分查找性能真的比普通遍历查找性能高吗?

苏子晨
  • 145

都说二分法查找是为了提高性能,可我在实际测试中发现所用时间要比普通遍历高不少
求教是不是代码有问题


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
回复
阅读 3.3k
3 个回答
Xeira
  • 4.1k
✓ 已被采纳

比较无聊,所以在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

现在看起来二分法的效率已经超过遍历了,所以应该是除法取整这个过程导致了二分法搜索效率的降低

在长度为n的有序数组中查找某一元素:

  • 顺序查找算法:时间复杂度最好的情况是O(1),最差情况为O(N);

  • 折半查找算法(二分法):时间复杂度为logN;

提到性能问题都是针对一定规模的数据量的(你测试的数据量偏少),在平均情况下,折半查找的效率比顺序查找高。

我简单看了下觉得代码问题不大,我在chrome中实际测试了下,确实比普通遍历花的时间要多,二分为5ms以内,普通遍历为1ms内。我觉得问题可能是数据量比较小,二分查找的优势没有体现出来。但是不至于像楼主测试的差一个数量级呀。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏