晚上看數據結構,順手用 JavaScript 寫了個二分查找演算法:
// 二分查找健忘遞歸版本
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 來計算初始 high 時才要考慮
return -1;
}
}
var arr = [1,2,3,4,5,6];
alert(binary_search(arr, 3, 0, arr.length-1));
按設想,它應該輸出查找目標的下標,但意想不到的事情發生了:只見 CPU 霎時狂轉,約兩秒後,瀏覽器自動終止了腳本的運行,留下一陣納悶。
根據經驗判斷,應該是腳本運行過程中出現了死循環。仔細看了看演算法,沒發現什麼問題(乾脆照著課本代碼輸入,總不會錯了吧),但問題依舊。於是就在第一個判斷條件裡加了個輸出語句:
function binary_search(arr, target, low, high){
if(low < high){ // 至少包括兩個元素
var min = (low + high) / 2;
// ...其餘邏輯同上
}
// ...
}
運行後彈出個對話框,裡面的數字是 2.5——突然有一種恍然大悟、同時又想要砸電腦的衝動。
JavaScript 裡的 "/" 運算符跟 C++ 裡的不一樣:後者會自動取整,前者若不能整除則會得到小數(比如 5/2 = 2.5)。在二分查找中,(low + high) / 2 得到 2.5 這樣的小數作為下標,導致陣列訪問異常、遞歸無法正常收斂,最終陷入死循環。
(1)var min = parseInt((low + high) / 2);
(2)var min = Math.floor((low + high) / 2);
這個小插曲提醒我們:從靜態類型語言轉到 JavaScript 時,除法運算的行為差異是一個很容易忽略、卻又十分致命的坑。凡是需要整數下標或取整的場景,一定要記得顯式地做取整處理。