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)的查找时间
• 结构最底层是完整的有序链表上层是下层的索引每层约一半节点
• 操作查找：从最高层开始，逐层下降插入：随机决定节点层数删除：删除所有层的节点
• 优势实现简单，比红