# 2.2.Binary Search

* **Introduction (參考自:** [**小殘的程式光廊**](http://emn178.pixnet.net/blog/post/88780407-%E4%BA%8C%E5%85%83%E6%90%9C%E7%B4%A2%E6%B3%95\(binary-search\))**)**
  * 二元搜索法(Binary Search)又稱折半搜索，搜索演算法的一種
  * 可使用Divide and Conquer或直接使用迴圈來實作
  * 搜索的目標資料必須是已經排序過的(以小到大排序為例)
* **作法**
  * 1.取出搜索範圍中點的元素。
  * 2.與搜索目標比較, 若相等則回傳位址. 

      若小於則將左邊邊界改為中點右側，若大於則將右邊邊界改為中點左側。
  * 3.左邊邊界不超過右邊邊界(還有資料)則重複以上動作，若已無資料則回傳-1(找不到)。
* **分析**
  * 最佳時間複雜度：O(1)
  * 平均時間複雜度：O(log n)
  * 最差時間複雜度：O(log n)
  * 空間複雜度：O(1)
* **程式碼**
  * [leetcode 33](https://jenhsuan.gitbooks.io/letcode/content/leetcode33-search-in-rotated-sorted-array.html)