DIV CSS 佈局教程網

JavaScript 中 / 運算符的常見錯誤陷阱
編輯:關於JavaScript     

晚上看數據結構,順手用 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 時,除法運算的行為差異是一個很容易忽略、卻又十分致命的坑。凡是需要整數下標或取整的場景,一定要記得顯式地做取整處理。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved