一、二分查找法
前提條件
- 數組已按升序排序
- 支持隨機訪問（數組/Vector/Deque）
算法流程
- 初始化
low=0, high=n-1
- 循環
while (low <= high)：
mid = (low + high) / 2
若 arr[mid] == target → 返回 mid
若 arr[mid] > target → high = mid - 1
若 arr[mid] < target → low = mid + 1
- 循環結束返回 -1（未找到）
C++ 實現
int binary_search(const int* arr, int n, int target) {
if (n <= 0) return -1;
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 防溢出寫法
if (arr[mid] == target) return mid;
else if (arr[mid] > target) high = mid - 1;
else low = mid + 1;
}
return -1;
}
二、二叉查找樹 (BST) 查找
BST 性質
- 左子樹所有節點值 < 根節點值
- 右子樹所有節點值 > 根節點值
- 左右子樹同為 BST
- 中序遍歷得升序序列
節點定義與建樹
struct BTreeNode {
int data;
BTreeNode* left;
BTreeNode* right;
BTreeNode(int v) : data(v), left(nullptr), right(nullptr) {}
};
BTreeNode* create_bst(int* arr, int n) {
if (n == 0) return nullptr;
BTreeNode* root = new BTreeNode(arr[0]);
for (int i = 1; i < n; ++i) {
BTreeNode* cur = root;
BTreeNode* parent = nullptr;
while (cur) {
parent = cur;
if (arr[i] < cur->data) cur = cur->left;
else cur = cur->right;
}
if (arr[i] < parent->data) parent->left = new BTreeNode(arr[i]);
else parent->right = new BTreeNode(arr[i]);
}
return root;
}
遞歸查找
bool bst_search(BTreeNode* root, int target) {
if (!root) return false;
if (root->data == target) return true;
else if (target < root->data) return bst_search(root->left, target);
else return bst_search(root->right, target);
}
三、總結對比
| 維度 | 二分查找 (數組) | BST 查找 |
|---|
| 前提 | 數組有序 | 樹滿足 BST 性質 |
|---|
| 時間複雜度 | O(log n) | O(h)，h 為樹高。平衡樹 O(log n)，退化鏈表 O(n) |
|---|
| 空間複雜度 | O(1) 迭代 / O(log n) 遞歸 | O(h) 遞歸棧 / O(1) 迭代 |
|---|
| 動態更新 | 插入/刪除 O(n) 需移動元素 | 插入/刪除 O(h)，適合頻繁更新場景 |
|---|
| 緩存友好度 | 極高（連續內存） | 較低（指針跳轉） |
|---|
| 適用場景 | 靜態數據、高頻查找、嵌入式 | 動態數據、需有序遍歷、範圍查詢 |
|---|
四、優化方向
- 二分查找：
std::binary_search/lower_bound/upper_bound (C++ STL)，避免手寫錯誤。
- BST：引入平衡機制（AVL、紅黑樹、Treap、Splay），保證
h = O(log n)。C++ std::map/std::set 內部即為紅黑樹。
- 海量數據：B+ 樹（磁盤友好）、跳表（並發友好）、布隆過濾器（快速判斷不存在）。
