c++建立一个无序表并实现对其顺序查找和折半查找

C++可以使用STL中的unordered_map来建立一个无序表，也可以手动实现哈希表。

顺序查找可以使用for循环遍历整个表，找到目标元素即返回其位置。折半查找则需要先将表按照关键字排序，然后使用二分法查找目标元素。

以下是一个简单的示例代码：

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

// 手动实现哈希表
class MyHashMap {
private:
    vector<pair<int, int>> data;
public:
    MyHashMap() {}

    void put(int key, int value) {
        for (auto& p : data) {
            if (p.first == key) {
                p.second = value;
                return;
            }
        }
        data.emplace_back(key, value);
    }

    int get(int key) {
        for (auto& p : data) {
            if (p.first == key) {
                return p.second;
            }
        }
        return -1;
    }
};

int main() {
    // 使用STL中的unordered_map
    unordered_map<int, int> umap;
    umap[1] = 10;
    umap[2] = 20;
    umap[3] = 30;
    cout << umap[2] << endl; // 输出20

    // 手动实现哈希表
    MyHashMap mymap;
    mymap.put(1, 10);
    mymap.put(2, 20);
    mymap.put(3, 30);
    cout << mymap.get(2) << endl; // 输出20

    // 顺序查找
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int target = 5;
    for (int i = ; i < nums.size(); i++) {
        if (nums[i] == target) {
            cout << "顺序查找：找到了，位置为" << i << endl;
            break;
        }
    }

    // 折半查找
    sort(nums.begin(), nums.end());
    int left = , right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            cout << "折半查找：找到了，位置为" << mid << endl;
            break;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ;
}