• 假如排序好的話，有一種比 linear search 這種從第一個找到最後一個更快速的演算法

  • 只需要一直切分對半，透過這種方式更快拿到目標。

  • 所謂的 binary 是二進制

  • 要注意的點，linear search 可以用在各種 array， 而 Binary Search 只能用在 sorted array

  • More efficient than linear search

  • 8 → 4 → 2 → 1， at most 3 steps to find what we want

  • 時間複雜度 Worst Case Performance：O(log n)

  • 時間複雜度 Best Case Performance： O(1)

  • 時間複雜度 Average performance：O(log n)

其實也不算完全初學，之前就有碰過類似概念，稍微做一下整理。

核心概念

Binary Search 是一種 在已排序資料中快速尋找目標值 的演算法。

它的核心就是 每次比較中間值，並把搜尋範圍縮小一半：

  1. 從整個資料範圍開始。

  2. 找到中間元素，和目標比較：

    • 如果相等 → 找到答案 。

    • 如果目標比較小 → 縮小到左半邊繼續找。

    • 如果目標比較大 → 縮小到右半邊繼續找。

  3. 重複這個步驟，直到找到目標或範圍縮小到空。

想像中有點像是在字典裡找一個字，因為字典是排好順序的，所以不會從第一頁慢慢找，會直接看什麼注音從那個部分開始找。

使用條件

  1. 必須是 已經排序好的資料（升序或降序都可以）。

  2. 可以快速存取（像陣列 Array）。

範例

1
[1, 3, 5, 7, 9, 11, 13];

我要找數字 9：

  1. 中間位置 → 7
    → 9 比 7 大，所以只要看右半邊 [9, 11, 13]

  2. 新的中間位置 → 11
    → 9 比 11 小，所以只要看左半邊 [9]

  3. 找到 9

最後**空間複雜度是 O(1)**（只需要幾個變數記錄範圍）。

General Guide of Algorithm Design

  • Implement some human thinking in algorithms

    • 在寫之前先用用大腦想一下怎麼去設計它

  • Don’t make the computer do dumb calculation or stupid things just because computer can do it

    • 不要因為電腦可以做到就都用很複雜的迴圈來解決，有時候不需要

Intersection problem

輸入 [1,2,3] , [5,16,1,3]

有沒有重複的交集 should return [1,3]

用 vue playground 來練習蠻方便的。

Counter

演算法的技巧。

  • this is a general skill when doing algorithm design. counter in not a formal name.

  • name is different everywhere, but the idea is the same.

  • 看每一個數字跑過的時間出現了幾次

Pointer

演算法的技巧。

  • this is a general skill when doing algorithm design. Pointer is not a formal name.

  • Name is different, but the idea is the same everywhere.

  • if helps reduce the complexity of algorithm.

counter 跟 pointer 在講什麼沒有到很了解，先記錄下來。