//二分查找健忘遞歸版本
復制代碼 代碼如下:
function binary_search(arr,target,low,high){
if(low<high){ //至少包括兩個元素
var min=(low+high)/2;
if(target>arr[min])
return binary_search(arr,target,min+1,high);
else
return binary_search(arr,target,low,min);
}else if(low==high){ //只剩下一個元素
if(arr[low]==target)
return low;
else return -1;
}else if(low>high){ //空，當用arr.length-1來計算arr的初始high時才要考慮
return -1;
}
}
var arr=[1,2,3,4,5,6];
alert(binary_search(arr,3,0,arr.length-1));
晚上看數據結構，順便就用js寫了個二分查找算法（代碼如上），然後隨便寫了個數組作為測試數據（如上），按照設想應該是輸出查找目標的下標，但是意向不到的事情發生了，只見CPU霎時狂轉，約兩秒後，浏覽器自動終止了腳本的運行，然後就一陣納悶。
根據經驗來看，應該是在腳本運行的過程出現了死循環，自習看了一下算法，沒有發現什麼問題（干脆直接照著課本上的代碼輸入總不會錯了吧），但是問題依舊。於是就在第一個判斷條件裡面加了個輸出語句，如下：
復制代碼 代碼如下:
//二分查找健忘遞歸版本function binary_search(arr,target,low,high){
if(low<high){ //至少包括兩個元素
var min=(low+high)/2;
if(target>arr[min])
return binary_search(arr,target,min+1,high);
else
return binary_search(arr,target,low,min);
}else if(low==high){ //只剩下一個元素
if(arr[low]==target)
return low;
else return -1;
}else if(low>high){ //空，當用arr.length-1來計算arr的初始high時才要考慮
return -1;
}
}
運行，彈出個對話框，裡面數字為2.5~~突然有種恍然大悟同時想要砸電腦的沖動。
出錯原因以及總結：
javascript裡面的"/"運算符跟C++裡面的"/"運算符不一樣，後者自動取整，前者若非整除則會得到小數（比如說5/2=2.5）。
解決方案：
（1）var min=parseInt((low+high)/2);
（2）var min=Match.floor((low+high)/2);