前言

查找（搜索）是笔试、机试、面试核心考点，分为静态查找（数据集不变）、动态查找（支持增删）两大类。 本文包含：顺序查找、二分查找、分块查找、二叉搜索树、平衡二叉树 AVL、红黑树（简述）、哈希查找、跳表，每种算法包含：

1. 算法原理
2. 时间 / 空间复杂度
3. 优缺点与适用场景
4. 完整可运行 C++ 代码
5. 细节易错点说明

一、静态查找（无插入删除，仅查询）

1. 顺序查找（线性查找）

原理

从头到尾逐个遍历数组，逐个比对关键字，找到返回下标，遍历完无匹配返回 - 1。 支持无序数组、有序数组。

复杂度

• 最好 O (1)，最坏 O (n)，平均 O (n)
• 空间 O (1)

优缺点

优点：实现简单、不要求有序； 缺点：大数据量效率极低。

C++ 实现

cpp

#include <iostream>
#include <vector>
using namespace std;

// 顺序查找，返回下标，无则-1
int seqSearch(vector<int>& arr, int key) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    int target = 9;
    int idx = seqSearch(arr, target);
    if (idx != -1)
        cout << "找到元素，下标：" << idx << endl;
    else
        cout << "未找到" << endl;
    return 0;
}

优化哨兵版（减少循环判断）

cpp

int seqSearchGuard(vector<int>& arr, int key) {
    arr.push_back(key); // 末尾放哨兵
    int i = 0;
    while (arr[i] != key) i++;
    arr.pop_back();
    return i == arr.size() ? -1 : i;
}

2. 二分查找（折半查找，仅有序数组）

原理

数组升序，每次取中间元素对比：

1. 中间值 == key：命中
2. 中间值 < key：去右半区间查找
3. 中间值 > key：去左半区间查找

复杂度

平均 / 最坏 O (logn)，空间迭代 O (1)、递归 O (logn)

适用场景

静态有序数组，无频繁插入删除

迭代版（推荐，无栈溢出）

cpp

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int key) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        // 防止溢出，等价 (l+r)/2
        int mid = l + (r - l) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {1,2,3,4,5,6,7,8,9};
    cout << binarySearch(arr, 6) << endl;
    return 0;
}

递归版二分

cpp

int binaryRec(vector<int>& arr, int l, int r, int key) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (arr[mid] == key) return mid;
    else if (arr[mid] < key)
        return binaryRec(arr, mid+1, r, key);
    else
        return binaryRec(arr, l, mid-1, key);
}

高频衍生题型代码

1. 查找左边界（第一个等于 key）

cpp

int leftBound(vector<int>& arr, int key) {
    int l = 0, r = arr.size()-1;
    int ans = -1;
    while(l <= r) {
        int mid = l + (r-l)/2;
        if(arr[mid] == key) {
            ans = mid;
            r = mid - 1;
        } else if(arr[mid] < key) l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

1. 查找右边界（最后一个等于 key）

cp

int rightBound(vector<int>& arr, int key) {
    int l = 0, r = arr.size()-1;
    int ans = -1;
    while(l <= r) {
        int mid = l + (r-l)/2;
        if(arr[mid] == key) {
            ans = mid;
            l = mid + 1;
        } else if(arr[mid] < key) l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

3. 分块查找（索引顺序查找）

原理

1. 数组分若干块，块内无序、块间有序；
2. 建立索引表：存储每块最大值、块起始下标；
3. 二分索引表确定目标块，块内顺序查找。

复杂度

索引二分 O (logm) + 块内顺序 O (s)，m 块、块大小 s

C++ 完整实现

cpp

#include <iostream>
#include <vector>
using namespace std;

// 索引结构体
struct Index {
    int maxVal;
    int start;
};

// 构建索引表
vector<Index> buildIndex(vector<int>& arr, int blockSize) {
    vector<Index> idx;
    int n = arr.size();
    for (int i = 0; i < n; i += blockSize) {
        Index tmp;
        tmp.start = i;
        int maxx = arr[i];
        int end = min(i + blockSize, n);
        for (int j = i; j < end; j++)
            maxx = max(maxx, arr[j]);
        tmp.maxVal = maxx;
        idx.push_back(tmp);
    }
    return idx;
}

int blockSearch(vector<int>& arr, vector<Index>& idx, int blockSize, int key) {
    // 二分索引找块
    int l = 0, r = idx.size()-1;
    int targetBlock = -1;
    while(l <= r) {
        int mid = l + (r-l)/2;
        if(idx[mid].maxVal >= key) {
            targetBlock = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if(targetBlock == -1) return -1;
    // 块内顺序查找
    int start = idx[targetBlock].start;
    int end = min(start + blockSize, (int)arr.size());
    for(int i = start; i < end; i++) {
        if(arr[i] == key) return i;
    }
    return -1;
}

int main() {
    vector<int> arr = {22,12,13,8,20,33,42,44,38,24,48,60,58,74,49};
    int block = 5;
    auto idx = buildIndex(arr, block);
    cout << blockSearch(arr, idx, block, 44) << endl;
    return 0;
}

二、动态查找（支持增、删、查，数据集可变）

4. 二叉搜索树 BST

性质

左子树所有节点 < 根 < 右子树所有节点；中序遍历升序。

复杂度

平衡时 O (logn)，极端有序数据退化成链表 O (n)

C++ 完整实现（增删查）

cpp

#include <iostream>
using namespace std;

struct BSTNode {
    int val;
    BSTNode* left;
    BSTNode* right;
    BSTNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 查找
BSTNode* bstSearch(BSTNode* root, int key) {
    if (!root || root->val == key) return root;
    if (key < root->val)
        return bstSearch(root->left, key);
    else
        return bstSearch(root->right, key);
}

// 插入
BSTNode* bstInsert(BSTNode* root, int key) {
    if (!root) return new BSTNode(key);
    if (key < root->val)
        root->left = bstInsert(root->left, key);
    else if (key > root->val)
        root->right = bstInsert(root->right, key);
    return root;
}

// 找最小值节点（删除用）
BSTNode* getMin(BSTNode* root) {
    while (root->left) root = root->left;
    return root;
}

// 删除节点
BSTNode* bstDelete(BSTNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val)
        root->left = bstDelete(root->left, key);
    else if (key > root->val)
        root->right = bstDelete(root->right, key);
    else {
        // 找到待删节点
        // 情况1：叶子 / 单孩子
        if (!root->left) {
            BSTNode* tmp = root->right;
            delete root;
            return tmp;
        }
        if (!root->right) {
            BSTNode* tmp = root->left;
            delete root;
            return tmp;
        }
        // 情况2：左右都有，取右子树最小替换
        BSTNode* minRight = getMin(root->right);
        root->val = minRight->val;
        root->right = bstDelete(root->right, minRight->val);
    }
    return root;
}

// 中序遍历
void inOrder(BSTNode* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

int main() {
    BSTNode* root = nullptr;
    root = bstInsert(root,5);
    root = bstInsert(root,3);
    root = bstInsert(root,7);
    root = bstInsert(root,1);
    root = bstInsert(root,4);
    inOrder(root);
    cout << endl;
    root = bstDelete(root,3);
    inOrder(root);
    return 0;
}

5. AVL 平衡二叉树（自平衡 BST）

核心规则

任意节点左右子树高度差（平衡因子）绝对值≤1；插入 / 删除失衡通过旋转恢复平衡。 旋转类型：LL、RR、LR、RL。

C++ 完整实现（增、查、旋转）

cpp运行

#include <iostream>
#include <algorithm>
using namespace std;

struct AVLNode {
    int val;
    int height;
    AVLNode* left;
    AVLNode* right;
    AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
};

int getHeight(AVLNode* root) {
    return root ? root->height : 0;
}

int getBalance(AVLNode* root) {
    return getHeight(root->left) - getHeight(root->right);
}

// 右旋 LL
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T = x->right;
    x->right = y;
    y->left = T;
    y->height = 1 + max(getHeight(y->left), getHeight(y->right));
    x->height = 1 + max(getHeight(x->left), getHeight(x->right));
    return x;
}

// 左旋 RR
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T = y->left;
    y->left = x;
    x->right = T;
    x->height = 1 + max(getHeight(x->left), getHeight(x->right));
    y->height = 1 + max(getHeight(y->left), getHeight(y->right));
    return y;
}

// 插入
AVLNode* avlInsert(AVLNode* root, int key) {
    if (!root) return new AVLNode(key);
    if (key < root->val)
        root->left = avlInsert(root->left, key);
    else if (key > root->val)
        root->right = avlInsert(root->right, key);
    else return root;

    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    int bal = getBalance(root);

    // LL
    if (bal > 1 && key < root->left->val)
        return rightRotate(root);
    // RR
    if (bal < -1 && key > root->right->val)
        return leftRotate(root);
    // LR
    if (bal > 1 && key > root->left->val) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    // RL
    if (bal < -1 && key < root->right->val) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

AVLNode* avlSearch(AVLNode* root, int key) {
    if (!root || root->val == key) return root;
    if (key < root->val) return avlSearch(root->left, key);
    return avlSearch(root->right, key);
}

void inOrder(AVLNode* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

int main() {
    AVLNode* root = nullptr;
    int arr[] = {10,20,30,40,50,25};
    for (int x : arr) root = avlInsert(root, x);
    inOrder(root);
    return 0;
}

6. 哈希查找（散列查找，平均 O (1)）

原理

哈希函数映射关键字到数组下标；冲突解决：链地址法、开放寻址。

方案 1：链地址法（C++ 实现，推荐）

cpp

#include <iostream>
#include <vector>
#include <list>
using namespace std;

const int MOD = 10;

// 哈希表：数组+链表
vector<list<int>> hashTable(MOD);

// 哈希函数
int hashFunc(int key) {
    return key % MOD;
}

// 插入
void hashInsert(int key) {
    int idx = hashFunc(key);
    hashTable[idx].push_back(key);
}

// 查找
bool hashSearch(int key) {
    int idx = hashFunc(key);
    for (int num : hashTable[idx]) {
        if (num == key) return true;
    }
    return false;
}

// 删除
void hashRemove(int key) {
    int idx = hashFunc(key);
    hashTable[idx].remove(key);
}

int main() {
    hashInsert(12);
    hashInsert(22);
    hashInsert(35);
    cout << boolalpha << hashSearch(22) << endl;
    hashRemove(22);
    cout << hashSearch(22) << endl;
    return 0;
}

方案 2：开放寻址法（线性探测）

cpp

#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 15;
const int EMPTY = -1;
vector<int> hashTable(SIZE, EMPTY);

int hashFunc(int k) { return k % SIZE; }

void insert(int key) {
    int idx = hashFunc(key);
    while (hashTable[idx] != EMPTY) {
        idx = (idx + 1) % SIZE;
    }
    hashTable[idx] = key;
}

bool search(int key) {
    int idx = hashFunc(key);
    int start = idx;
    while (hashTable[idx] != EMPTY) {
        if (hashTable[idx] == key) return true;
        idx = (idx + 1) % SIZE;
        if (idx == start) break;
    }
    return false;
}

7. 跳表 SkipList（Redis ZSet 底层）

原理

多层有序链表，上层作为索引加速查找，平均 O (logn)；无需平衡旋转，实现比 AVL / 红黑树简单。 简化 C++ 极简实现：

cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

#define MAX_LEVEL 5

struct SkipNode {
    int val;
    vector<SkipNode*> next;
    SkipNode(int v, int level) : val(v), next(level, nullptr) {}
};

class SkipList {
private:
    SkipNode* head;
    int curLevel;
    // 随机层数
    int randomLevel() {
        int lvl = 1;
        while (rand() % 2 == 0 && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }
public:
    SkipList() {
        srand((unsigned)time(NULL));
        head = new SkipNode(-1, MAX_LEVEL);
        curLevel = 1;
    }

    // 查找
    bool search(int key) {
        SkipNode* p = head;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (p->next[i] && p->next[i]->val < key)
                p = p->next[i];
        }
        p = p->next[0];
        return p && p->val == key;
    }

    // 插入
    void insert(int key) {
        vector<SkipNode*> update(MAX_LEVEL, nullptr);
        SkipNode* p = head;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (p->next[i] && p->next[i]->val < key)
                p = p->next[i];
            update[i] = p;
        }
        int newLvl = randomLevel();
        SkipNode* newNode = new SkipNode(key, newLvl);
        for (int i = 0; i < newLvl; i++) {
            newNode->next[i] = update[i]->next[i];
            update[i]->next[i] = newNode;
        }
        if (newLvl > curLevel) curLevel = newLvl;
    }
};

int main() {
    SkipList sl;
    sl.insert(3);
    sl.insert(1);
    sl.insert(5);
    cout << boolalpha << sl.search(3) << endl;
    return 0;
}

三、所有查找算法对比汇总

表格

算法	平均查找	最坏查找	插入删除	是否有序	适用场景
顺序查找	O(n)	O(n)	O(n)	无序 / 有序	少量数据、链表
二分查找	O(logn)	O(logn)	O(n)	有序静态数组	固定不变有序数组
分块查找	O(logm+s)	O(logm+s)	O(n)	块间有序	大数据静态表
BST	O(logn)	O(n)	O(logn)	动态有序	小规模动态数据
AVL 平衡树	O(logn)	O(logn)	O(logn)	动态有序	频繁查改，要求稳定复杂度
哈希查找	O(1)	O(n)	O(1)	无序	缓存、键值映射
跳表	O(logn)	O(logn)	O(logn)	动态有序	Redis 有序集合

四、核心考点细节总结

1. 二分查找必须有序，只适用于数组，链表不能二分；
2. BST 退化根源：有序数据连续插入，平衡树解决该问题；
3. 哈希查找优势是平均常数级，但存在哈希冲突最坏退化；
4. AVL 平衡因子严格 ±1，旋转多；红黑树放宽平衡条件，工业更常用；
5. 跳表用多层链表替代平衡树，无复杂旋转，工程实现简单；
6. 静态查找适合一次性构建、极少修改场景；动态查找支持频繁增删。