返回列表

Javascript二分搜索的实现Binary Search

默认分类 2011-01-12 22:20:35

闲来无事,回想起去年年初应聘某公司被问及如何实现二分法,回答说可以用循环实现时被嗤之以鼻,一直心有不甘,二分法难道能且只能用递归实现吗?带着这个疑问亲自动手实验了一下,使用循环完全可以实现.

递归实现:

var d = [1,2,3,4,5,6,7,8,9];
function bSearch(b,ar,st){
    if(ar.length<1||b<ar[0]||b>ar[ar.length-1]) {return -1;}
    if(!st) st=0;
    var m = Math.floor(ar.length/2);

    if(b==ar[m]) { return m+st; }
    else if(b<ar[m]) { return arguments.callee(b,ar.slice(0,m),st); }
    else if(b>ar[m]) {
        return arguments.callee(b,ar.slice(m,ar.length),m+st);
    }
}
alert(bSearch(1,d,0));

循环实现:

var d = [1,2,3,4,5,6,7,8,9];
function bSearch2(b,ar){
    var st=0,en=ar.length-1,m;
    for(var i=0;i<ar.length;i++)
    {
        if(st>=en||b<ar[st]||b>ar[en]) {return -1;}

        m = Math.floor((st+en)/2);
        if(b==ar[m]) return m;
        else if(b<ar[m]) en=m;
        else if(b>ar[m]) st=m;
    }
    return -1;
}
alert(bSearch2(1,d,0));