第三题

struct flat_map {
    struct {
        int key;
        int value;
    } bucket[65536];
    int size = 0;

    struct result {
        int index;
        bool hit;
    };
    result find(int begin, int end, int key) {
        if (begin == end)
            return {begin, false};
        else {
            int mid = begin + (end - begin) / 2;
            if (key < bucket[mid].key)
                return find(begin, mid, key);
            else if (bucket[mid].key < key)
                return find(mid+1, end, key);
            else
                return {mid, true};
        }
    }

    int get(int key) {
        result p = find(0, size, key);
        if (p.hit)
            return bucket[p.index].value;
        else
            return 0;
    }

    void put(int key, int value) {
        result p = find(0, size, key);
        for (int i = size; i > p.index; --i)
            bucket[i] = bucket[i - 1];
        size++;
        bucket[p.index].key = key;
        bucket[p.index].value = value;
    }
};

判断题

若数组 bucket 的下标在 [b, e) 范围内存在键 k，find(b, e, k) 函数返回的 hit 为 false（ ）。

{{ select(1) }}

• 正确
• 错误