c++ - 在排序数组中搜索，比较少

Question

给你一个 std::vector<T>不同的项目。已经排序了。输入 T只支持小于 <运算符进行比较。这是一个繁重的功能。所以你必须尽可能少地使用它。

有没有比二分查找更好的解决方案？如果不是，有没有比这更好的解决方案，使用 less-than 运算符的次数更少？

template<typename T>
int FindKey(const std::vector<T>& list, const T& key)
{
    if( list.empty() )
        return -1;

    int left = 0;
    int right = list.size() - 1;
    int mid;

    while( left < right )
    {
        mid = (right + left) / 2;
        if( list[mid] < key )
            left = mid + 1;
        else
            right = mid;
    }

    if( !(key < list[left]) && !(list[left] < key) )
        return left;    

    return -1;
}

这不是真实世界的情况，只是编码测试。

Answer 1

您可以使用 hash table 权衡额外的 O(n) 预处理时间以获得摊销的 O(1) 查询时间(例如 unordered_map )创建一个 lookup table .

哈希表计算 hash functions键，不要比较键本身。

两个键可能具有相同的散列，导致冲突，这解释了为什么不能保证每个单独的操作都是常数时间。 Amortized常数时间意味着如果你执行 k 操作总共花费时间 t，那么商 t/k = O(1)，对于足够大的 k。

Live example :

#include <vector>
#include <unordered_map>
 
template<typename T>
class lookup {
  std::unordered_map<T, int> position;
public:
  lookup(const std::vector<T>& a) {
    for(int i = 0; i < a.size(); ++i) position.emplace(a[i], i);
  }
  int operator()(const T& key) const {
    auto pos = position.find(key);
    return pos == position.end() ? -1 : pos->second;
  }
};

这也需要额外的内存。

如果值可以映射到整数并且在 a reasonable range 范围内(即 max-min = O(n))，您可以简单地使用 vector作为查找表而不是 unordered_map .受益于保证恒定的查询时间。

另见 answer to "C++ get index of element of array by value" ，以获得更详细的讨论，包括线性、二进制和哈希索引查找的经验比较。

更新

如果接口(interface)类型为T除bool operator<(L, R) 外不支持其他操作, 然后使用 decision tree model你可以证明 lower bound for comparison-based search algorithms为 Ω(log n)。