[演算法(Algorithm)] 二分搜尋法(Binary Search)

• 對於已排序好的資料，利用已排序的特性來加快搜尋速度
• 二分搜尋法(Binary Search)
  • 資料需依大小先排序好
  • Middle = ⌊(Left + Right)/2⌋
  • 將鍵值key與搜尋範圍的中間資料data[Middle]作比對
    • key = data[Middle]：找到
    • key < data[Middle]：縮小搜尋範圍 Right = Middle-1
    • key > data[Middle]：縮小搜尋範圍 Left = Middle+1
  • 重複上步驟，直到找到資料或搜尋範圍交叉(找不到)
• 特性：
  • 資料需事先排序
  • 支援隨機存取(Random Access)機制
  • 時間複雜度為Ο(log₂n)
• 時間複雜度(Time Complexity)
  • T(n) = T(n/2) + Ο(1) = Ο(log₂n)
• Demo:
• 演算法
  • JS

  var binarySearch = function(data, key) {
      var left = 0;
      var right = data.length - 1;
      var middle = 0;
      while(left <= right){
          middle = parseInt((left+right)/2);
          if(data[middle] == key)
              return middle;
          else if(data[middle] < key)
              left = middle + 1;
          else                           //if(data[middle] > key)
              right = middle - 1;	
      }
      return -1; 
  }
  
  //執行
  var data = getRandomData();
  quickSort(data, 0, data.length-1);
  binarySearch(data, 5);