javascript資料結構與演算法之檢索演算法_javascript技巧

找出資料有2種方式，順序查找和二分查找。順序尋找適用於元素隨機排列的清單。二分查找適用於元素已排序的清單。二分查找效率更高，但是必須是已經排好序的列表元素集合。

一：順序查找
順序查找是從列表的第一個元素開始逐個列表元素判斷，直到找到了想要的結果，或是直到列表的結尾都沒有找到想要找的元素。

程式碼如下：

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;
}

二：找出最小值和最大值

在陣列中找出最小值演算法如下：

   1. 將數組第一個元素賦值給一個變量，把這個變數當作最小值。
   2. 開始遍歷數組，從第二個元素依序和當前最小值進行比較。
   3. 如果目前元素的數值小於目前最小值，則將目前元素設為新的最小值。
   4. 移到下一個元素，重複步驟3.
   5.  當程式結束時，這個變數中儲存的就是最小值。

程式碼如下：

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).
 2. 將陣列的最後一個元素所在的位置設定為上邊界(數組的長度減1)。
 3. 若下邊界等於或小於上邊界，則做如下：
    A. 將中點設定為(上邊界加上下邊界) 除以2.
    B. 若中點的元素小於查詢的值，則將下邊界設為中點元素所在下標加1.
    C. 如果中點的元素大於查詢的值，則將上邊界設定為中點元素所在下標減1.
    D. 否則中點元素即為要找出 的數據，可以進行回傳。

程式碼如下：

// 二分查找算法
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));

四：計算重複次數；
當二分查找演算法binSearch()函數找到某個值時，如果在資料集中還有其他相同的值出現，那麼該函數會定位在類似值附近，換句話說，其他相同的值可能會出現已找到數值的左邊或右邊。

那麼我們最簡單的方案就是寫2個循環，一個同時對資料集向下遍歷或向左遍歷，統計重複次數；然後，向上或向右遍歷，統計重複次數。程式碼如下：

// 计算重复次数
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 i = position + 1; i < arr.length; ++i) {
      if(arr[i] == 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);

如下圖：