DIV CSS 佈局教程網

用 JavaScript 實作二分搜尋法
編輯:JavaScript基礎知識     

二分搜尋(Binary Search)是查找有序資料的經典演算法:每次拿中間元素與目標比較,據此把搜尋範圍砍半,因此效率遠優於逐個比對。

使用前提只有一個:陣列必須是已經排序好的。

下面用遞迴的方式實作:

<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<script type="text/javascript">

  // window.alert(Math.floor(5.7));  // 向下取整 輸出 5

  // 二分查找法 陣列必須是有序的
  function binarySeach(arr, findval, leftIndex, rightIndex) {

    // 找到中間的值
    var midIndex = Math.floor((leftIndex + rightIndex) / 2);
    var midval = arr[midIndex];

    // 防止無窮遞歸
    if (leftIndex > rightIndex) {
      // 說明找不到
      document.writeln("找不到");
      return;
    }

    // 進行查找
    if (midval > findval) {
      // 在左邊找
      binarySeach(arr, findval, leftIndex, midIndex - 1);
    } else if (midval < findval) {
      // 說明往右邊找
      binarySeach(arr, findval, midIndex + 1, rightIndex);
    } else {
      // 找到了 輸出或者返回
      document.writeln("找到了,下標為:" + midIndex);
      return;
    }
  }

  var arr = [1, 3, 12, 21, 24, 44, 54, 67];
  binarySeach(arr, 67, 0, arr.length - 1);
</script>
</head>
<body></body>
</html>

幾個實作重點

整數除法:用 Math.floor() 把索引夾在中點,確保 midIndex 一定是整數。

遞迴的終止條件:leftIndex > rightIndex 代表範圍已經交叉,說明目標不存在。少了這個判斷,遞迴會無止境地進行下去。

範圍的收斂方式:往左找時右端點是 midIndex - 1,往右找時左端點是 midIndex + 1。這裡必須加減一,否則在只剩兩個元素的情況下會陷入無限遞迴。

以 [1, 3, 12, 21, 24, 44, 54, 67] 搜尋 67 為例,第一次取索引 3(值 21),目標更大所以往右;接著取索引 5(值 44),仍往右;最後取到索引 7,命中並輸出下標。

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