Data structure & Algorithm
  • Initial page
  • 1212
  • 121231
  • 2.algorithm
    • 2.1.backtracking
      • 2.1.1.連續序列的排列組合(可能會重複)
      • 2.1.3.一串數列中任取n個數字, 總共有幾種組合
      • 2.1.2.一串數列中取n個數字, 共有幾種組合
    • 2.5.Quick sort
    • 2.6.2.6.廣度優先搜尋 (Breadth-first Search)
    • 2.2.Binary Search
    • 2.1.Backtracking
    • 2.4.河內塔 (Tower of Hanoi)
    • 2.7.動態規劃
    • 2.8.深度優先搜尋 (Depth-first Search)
    • 2.7.二分搜尋法
    • 2.3.分治法 (Divide and Conquer)
  • 2.Count and Say
  • 1.Leetcode Algorithm Practice
  • 2-count-and-say
    • c-solution
    • javascript-solution
  • Algorithm
  • 123
Powered by GitBook
On this page

Was this helpful?

  1. 2.algorithm

2.2.Binary Search

Previous2.6.2.6.廣度優先搜尋 (Breadth-first Search)Next2.1.Backtracking

Last updated 5 years ago

Was this helpful?

  • Introduction (參考自: )

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

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

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

  • 作法

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

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

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

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

  • 分析

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

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

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

    • 空間複雜度：O(1)

  • 程式碼

小殘的程式光廊
leetcode 33