给你一个 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;
}
这不是真实世界的情况,只是编码测试。
最佳答案
您可以使用 hash table 权衡额外的 O(n) 预处理时间以获得摊销的 O(1) 查询时间(例如 unordered_map
)创建一个 lookup table .
哈希表计算 hash functions键,不要比较键本身。
两个键可能具有相同的散列,导致冲突,这解释了为什么不能保证每个单独的操作都是常数时间。 Amortized常数时间意味着如果你执行 k 操作总共花费时间 t,那么商 t/k = O(1),对于足够大的 k。
#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)。
关于c++ - 在排序数组中搜索,比较少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33936076/