c++检索算法的实现

在C++中，检索算法通常涉及到数据结构的选择和操作，常见的有线性搜索、二分查找、哈希表等。这里简单介绍一下几种基本的检索算法：

1. **线性搜索**（Linear Search）：遍历整个列表逐个元素比较，适用于小规模数据或者无序列表。基本步骤是初始化索引为0，然后依次检查每个元素，直到找到目标值或者遍历完整个数组。

int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1; // 如果没找到则返回-1
}

2. **二分查找**（Binary Search）：适用于已排序的数据，通过每次将搜索范围缩小一半来提高效率。首先确定中间位置，如果中间元素等于目标，则返回该位置；如果小于目标，继续在右半部分搜索；反之在左半部分。

int binary_search(int arr[], int left, int right, int target) {
    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;
}

3. **哈希表**（Hash Table）：通过哈希函数直接定位到存储位置，可以在常数时间内完成查找，但需要额外的空间开销，并且对冲突处理得当。

#include <unordered_map>
std::unordered_map<int, int> hash_table;

// 插入和查找
void insert(int key, int value) {
    hash_table[key] = value;
}

int search(int key) {
    auto it = hash_table.find(key);
    if (it != hash_table.end())
        return it->second;
    else
        return -1;
}