Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


搜尋演算法 2 - Binary Search ( 二元搜尋法 )

By Jimmy 2022-04-25
發表於 演算法 資工
搜尋演算法 2 - Binary Search ( 二元搜尋法 )

Binary search 是在已排序好的陣列中最常用的其中一個搜尋演算法。

1. Binary Search 原理解釋

通常如果一個陣列已經排列好的話,就不會再用 linear search 來搜尋目標元素,因為一個一個迭代元素,效率實在太差。Binary Search 的原理是:每次會先和陣列中間的元素比較,因此每次比較會有三個結果:

第三個結果就是找到目標元素,因此就不用繼續再搜尋陣列了。前兩種的話:中間元素比目標元素大:就搜尋左半部的陣列 ( 假設陣列已經由小到大排列 ),中間元素比目標元素小:就搜尋右半部的陣列,並且重複用中間元素來和目標元素比較。

2. JavaScript 實作

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    }
  }
  return -1;
}

3. Time Complexity

最佳的情況就是第一次切割的時候就找到目標元素了,因此時間複雜度是 O(1)。

最差的情況,陣列需要分割 log2n (因為每次減少一半的搜尋長度),因此時間複雜度是 O(log n)。

最佳:O(1)
最差:O(log n)
平均:O(log n)

4. 參考資料

資料結構與演算法 (JavaScript)


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More