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

建立一个无序表，可以使用数组或链表等数据结构来实现。对于顺序查找，可以遍历整个表，逐个比较查找元素和表中元素是否相等，直到找到或遍历完整个表为止。对于折半查找，需要先将表中元素按照一定的顺序排列，通常是从小到大或从大到小。然后，每次将查找范围缩小一半，直到找到或查找范围为空为止。折半查找的时间复杂度为O(log n)，比顺序查找更快。

相关问题

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 ;
}

建立一个顺序表，输入一个关键字，对该表进行顺序查找和折半查找。

建立一个顺序表，可以使用数组或链表来实现。输入一个关键字后，可以通过顺序查找或折半查找来查找该关键字在表中的位置。

顺序查找是从表的第一个元素开始逐个比较，直到找到目标元素或者遍历完整个表。时间复杂度为O(n)。

折半查找是在有序表中进行查找，每次将查找区间缩小一半，直到找到目标元素或者区间为空。时间复杂度为O(log n)。

需要注意的是，顺序查找适用于表长度较小或者无序的情况，而折半查找适用于表长度较大且有序的情况。