C++查找算法面试题

1. 二分查找的原理和实现？

答案：

前提条件数组必须有序支持随机访问
原理每次比较中间元素根据比较结果缩小一半搜索范围时间复杂度：O(log n)
迭代实现

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

递归实现

int binarySearch(vector<int>& arr, int left, int right, int target) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        return binarySearch(arr, mid + 1, right, target);
    else
        return binarySearch(arr, left, mid - 1, target);
}

注意事项使用 left + (right - left) / 2 避免溢出注意边界条件循环不变量

2. 二分查找的变体有哪些？

答案：

查找第一个等于target的位置

int findFirst(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续向左找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

查找最后一个等于target的位置

int findLast(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // 继续向右找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

查找第一个大于等于target的位置（lower_bound）
查找第一个大于target的位置（upper_bound）

3. 哈希查找的原理？如何设计哈希函数？

答案：

原理通过哈希函数将键映射到数组索引直接访问，O(1)时间复杂度需要处理冲突
好的哈希函数特点计算简单快速均匀分布，减少冲突确定性（相同输入相同输出）
常见哈希函数除留余数法：hash(key) = key % M乘法哈希：hash(key) = (A * key) % M字符串哈希：

int hashString(string s) {
    int hash = 0;
    for (char c : s) {
        hash = hash * 31 + c;
    }
    return hash;
}

STL的hash为基本类型提供默认哈希函数可以自定义hash函数

4. 布隆过滤器是什么？

答案：

定义空间效率高的概率型数据结构用于判断元素是否在集合中可能误判（false positive），但不会漏判
原理使用位数组和多个哈希函数插入：多个哈希函数计算位置，置1查询：检查所有位置是否都为1
特点空间效率极高不支持删除（可用计数布隆过滤器）有误判率，可通过增加位数组大小降低
应用网页URL去重垃圾邮件过滤缓存穿透防护数据库查询优化

5. 跳表是什么？

答案：

定义有序链表的扩展通过多层索引实现快速查找平均O(log n)的查找时间
结构最底层是完整的有序链表上层是下层的索引每层约一半节点
操作查找：从最高层开始，逐层下降插入：随机决定节点层数删除：删除所有层的节点
优势实现简单，比红黑树容易支持范围查询并发性能好
应用Redis的有序集合（zset）LevelDB、RocksDB

学习专栏: https://www.nowcoder.com/creation/manager/columnDetail/MJ4oG8

6. 字典树（Trie）是什么？

答案：

定义也叫前缀树用于存储字符串集合共享公共前缀
结构

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd;
    TrieNode() : isEnd(false) {}
};

操作插入：O(m)，m是字符串长度查找：O(m)前缀查询：O(m)
应用自动补全拼写检查IP路由字符串匹配
优缺点优点：前缀查询快缺点：空间占用大

7. KMP算法的原理是什么？

答案：

问题字符串模式匹配在文本串中查找模式串
暴力算法逐个位置尝试匹配时间复杂度：O(m*n)
KMP优化利用已匹配信息，避免重复比较使用next数组（部分匹配表）时间复杂度：O(m+n)
next数组next[i]表示模式串前i个字符的最长相同前后缀长度失配时，模式串跳转到next[j]位置
实现

vector<int> getNext(string pattern) {
    int m = pattern.size();
    vector<int> next(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j])
            j = next[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        next[i] = j;
    }
    return next;
}

int kmp(string text, string pattern) {
    vector<int> next = getNext(pattern);
    int j = 0;
    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && text[i] != pattern[j])
            j = next[j - 1];
        if (text[i] == pattern[j])
            j++;
        if (j == pattern.size())
            return i - j + 1;
    }
    return -1;
}

8. 并查集是什么？如何实现？

答案：

定义Union-Find数据结构处理不相交集合的合并和查询判断元素是否在同一集合
操作find：查找元素所属集合union：合并两个集合
实现

class UnionFind {
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // 路径压缩
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        
        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

优化路径压缩：find时将节点直接连到根按秩合并：将小树连到大树
应用判断图的连通性最小生成树（Kruskal算法）社交网络

9. 线段树是什么？

答案：

定义用于区间查询和修改二叉树结构每个节点表示一个区间
操作区间查询：O(log n)单点修改：O(log n)区间修改：O(log n)（懒惰标记）
应用区间求和区间最值区间更新
基本实现

class SegmentTree {
    vector<int> tree;
    int n;
    
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(2*node, start, mid, l, r) +
               query(2*node+1, mid+1, end, l, r);
    }
};

10. 树状数组（Fenwick Tree）是什么？

答案：

定义也叫Binary Indexed Tree（BIT）用于高效计算前缀和比线段树简单
操作单点修改：O(log n)前缀和查询：O(log n)区间和：query(r) - query(l-1)
实现

class FenwickTree {
    vector<int> tree;
    int n;
public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
    
    void update(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & (-i);  // 加上lowbit
        }
    }
    
    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i);  // 减去lowbit
        }
        return sum;
    }
};