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

Question

你得到了 std::vector<T> 个不同的项目。已经排序了。 type 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

您可以使用 std::lower_bound。它通过 log(n)+1 比较来完成，这是您的问题的最佳复杂性。

template<typename T>
int FindKey(const std::vector<T>& list, const T& key)
{
  if(list.empty())
    return -1;
  typename std::vector<T>::const_iterator lb =
        std::lower_bound(list.begin(), list.end(), key);
  // now lb is an iterator to the first element
  // which is greater or equal to key
  if(key < *lb)
    return -1;
  else
    return std::distance(list.begin(), lb);
}

通过额外的相等性检查，您可以通过 log(n)+2 比较来完成。

Answer 2

您可以权衡额外的 O(n) 预处理时间以摊销 O(1) 查询时间，使用 hash table (e.g. an unordered_map) to create a lookup table.

哈希 tables 计算键的 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 作为查找 table 而不是 unordered_map。得益于保证恒定的查询时间。

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

更新

如果类型T的接口不支持除bool operator<(L, R)以外的其他操作，则使用decision tree model you can prove a lower bound for comparison-based search algorithms为Ω(log n)。

Answer 3

如果您的数字呈正态分布，您可以在 log log n 次中使用插值搜索。如果他们有其他发行版，您可以修改它以将您的发行版考虑在内，但我不知道哪些发行版会产生日志记录时间。

https://en.wikipedia.org/wiki/Interpolation_search

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

Search in sorted array with few comparisons

c++

algorithm

search

sorted

更新