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