2.2.Binary Search

• Introduction (參考自: 小殘的程式光廊)

  • 二元搜索法(Binary Search)又稱折半搜索，搜索演算法的一種

  • 可使用Divide and Conquer或直接使用迴圈來實作

  • 搜索的目標資料必須是已經排序過的(以小到大排序為例)

• 作法

  • 1.取出搜索範圍中點的元素。

  • 2.與搜索目標比較, 若相等則回傳位址.

    若小於則將左邊邊界改為中點右側，若大於則將右邊邊界改為中點左側。

  • 3.左邊邊界不超過右邊邊界(還有資料)則重複以上動作，若已無資料則回傳-1(找不到)。

• 分析

  • 最佳時間複雜度：O(1)

  • 平均時間複雜度：O(log n)

  • 最差時間複雜度：O(log n)

  • 空間複雜度：O(1)

• 程式碼

  • leetcode 33