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