DIV CSS 佈局教程網

JavaScript 數據結構與算法:順序查找與二分查找
編輯:JavaScript綜合知識     

查找是最基礎的算法之一。實踐中主要有兩種方式:順序查找適用於元素隨機排列的列表;二分查找適用於已排序列表,效率更高,但代價是必須先完成排序,且插入刪除成本高。

一、順序查找

從列表第一個元素開始逐個比較,直到找到目標或遍歷到末尾。

function seqSearch(data, arr) {
  for (var i = 0; i < arr.length; ++i) {
    if (arr[i] == data) {
      return true;
    }
  }
  return false;
}

實務中更有用的是返回位置的版本:

function seqSearch(data, arr) {
  for (var i = 0; i < arr.length; ++i) {
    if (arr[i] == data) {
      return i;
    }
  }
  return -1;
}

二、查找最小值與最大值

思路一致:先把首元素當作當前最值,然後遍歷其餘元素逐一比較,遇到更合適的就更新。

function findMin(arr) {
  var min = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] < min) { min = arr[i]; }
  }
  return min;
}

function findMax(arr) {
  var max = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] > max) { max = arr[i]; }
  }
  return max;
}

三、二分查找

算法步驟:

  1. 把首位置設為下邊界(0),末位置設為上邊界(長度 − 1)。
  2. 當下邊界不大於上邊界時循環:取中點 Math.floor((上界 + 下界) / 2)。
  3. 中點值小於目標,下邊界移到中點 + 1;中點值大於目標,上邊界移到中點 − 1;相等則返回。
function binSearch(data, arr) {
  var lowerBound = 0;
  var upperBound = arr.length - 1;

  while (lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound) / 2);
    if (arr[mid] < data) {
      lowerBound = mid + 1;
    } else if (arr[mid] > data) {
      upperBound = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

配合快速排序使用(這裡用最直觀的分區寫法便于理解):

function qSort(list) {
  if (list.length == 0) { return []; }

  var left = [];    // 小於基準值
  var right = [];   // 大於基準值
  var pivot = list[0];

  for (var i = 1; i < list.length; i++) {
    if (list[i] < pivot) { left.push(list[i]); }
    else { right.push(list[i]); }
  }

  return qSort(left).concat(pivot, qSort(right));
}

var numbers = [0, 9, 1, 8, 7, 6, 2, 3, 5, 4];
var list = qSort(numbers);
console.log(binSearch(6, list));   // 6

四、統計重複出現次數

二分查找找到某個值後,只保證停在「其中一個」匹配位置上。如果數據集中還有其他相同值,它們可能分布在該位置的左側或右側。因此需要用兩個循環向兩邊掃描:

function count(data, arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data, arr);

  if (position > -1) {
    ++count;
    arrs.push({ "index": count });

    // 向左掃描
    for (var i = position - 1; i >= 0; --i) {
      if (arr[i] == data) {
        ++count;
        arrs.push({ "index": count });
      } else {
        break;      // 遇到不同的值立即停止
      }
    }

    // 向右掃描
    for (var j = position + 1; j < arr.length; ++j) {
      if (arr[j] == data) {
        ++count;
        arrs.push({ "index": count });
      } else {
        break;
      }
    }
  }
  return arrs;
}

var arr = [0, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var arrs = count(1, arr);
console.log(arrs);
console.log(arrs.length);

由於有序數組中相同元素必然相鄰,掃描時一旦遇到不同的值就可以 break,不必遍歷全表。這是「有序」這個前提帶來的額外紅利。

如果要求更高性能(比如統計百萬級數據中的中位數或眾數),可以改寫二分查找使其返回「第一個等於目標的位置」和「最後一個等於目標的位置」,兩者下標之差加一即為出現次數,時間複雜度可壓到 O(log n)。

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