[DSA] Binary Search 以及 BST

**Binary Search** (二分搜尋) 和**BST** (二叉搜尋樹, Binary Search Tree)：

---

**Binary Search (二分搜尋)**

**定義：** 

- 二分搜尋是一種在已排序的數組或列表中查找特定值的算法。

**基本步驟：**

1. 找到中間元素。

2. 如果中間元素與目標值匹配，則返回其索引。

3. 如果中間元素小於目標值，則在右半部分（中間之後）重複上述步驟。

4. 如果中間元素大於目標值，則在左半部分（中間之前）重複上述步驟。

**時間複雜度：** 

- 最差情況和平均情況下的時間複雜度為 \(O(\log n)\)，其中 n 是列表或數組的大小。

---

**BST (Binary Search Tree, 二叉搜尋樹)**

**定義：** 

- 二叉搜尋樹是一種節點的二叉樹結構，其中每個節點都有一個可比較的鍵（和相關的值），並且滿足以下性質：

  - 左子樹中的所有鍵都小於節點的鍵。

  - 右子樹中的所有鍵都大於節點的鍵。

**基本操作：**

1. **插入 (Insert)**: 在 BST 中插入一個新鍵。

2. **查找 (Search)**: 檢查 BST 中是否存在特定的鍵。

3. **刪除 (Delete)**: 從 BST 中刪除指定的鍵。

4. **中序遍歷 (In-order Traversal)**: 遍歷 BST 的方法之一，結果是按鍵的升序訪問所有節點。

**時間複雜度：**

- 在平衡的 BST 中，插入、查找和刪除的時間複雜度均為 \(O(\log n)\)。但在最差情況下（例如當樹成為一個“鏈”時），這些操作的時間複雜度為 \(O(n)\)。

**註：**

- 為了確保 BST 的高效性，常常使用平衡技術，如 AVL 樹或紅黑樹，來確保樹保持大致平衡，從而保持操作的 \(O(\log n)\) 時間複雜度。

---

總結：雖然 Binary Search 和 BST 都與“二分”這一概念相關，但前者是一種在已排序的數組中查找元素的算法，而後者是一種數據結構，用於保存和檢索鍵值對。