Поиск в отсортированном массиве с несколькими сравнениями
Вам дают std::vector<T> отдельных предметов. который уже отсортирован.
тип T только поддерживает меньше, чем < оператор для сравнения. и это тяжелая функция. так что вы должен используйте его как можно меньше раз.
Есть ли лучшее решение, чем бинарный поиск?
Если нет, есть ли лучшее решение, чем это, которое использует оператор меньше, чем меньше раз?
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;
}
Это не реальная ситуация в мире, просто тестирование кода.
Решение
Вы могли бы обменять дополнительные На) время предварительной обработки для амортизации O (1) время запроса, используя хеш-таблица (например, unordered_map) создать Справочная таблица.
Хеш-таблицы вычисляют хеш-функции из ключей и не сравнивайте сами ключи.
Два ключа могут иметь одинаковый хеш, в результате чего столкновение, объяснение, почему не гарантируется, что каждая отдельная операция имеет постоянное время. амортизированный постоянное время означает, что если вы выполняете К операции, которые заняли время T в общем, то частное t / k = O (1), для достаточно большого К.
#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;
}
};
Это также требует дополнительной памяти.
Если значения могут быть сопоставлены с целыми числами и находятся в пределах разумный диапазон (Т.е. max-min = O (n)), вы можете просто использовать vector в качестве справочной таблицы вместо unordered_map, С пользой гарантированный постоянное время запроса.
Смотрите также это ответ на «C ++ получить индекс элемента массива по значению», для более подробного обсуждения, включая эмпирическое сравнение линейного, двоичного и хеш-индекса.
Если интерфейс типа T не поддерживает никаких других операций, кроме bool operator<(L, R)затем с помощью модель дерева решений Вы можете доказать нижняя граница для алгоритмов поиска на основе сравнения быть Ω (log n).
Другие решения
Ты можешь использовать 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 сравнения.
Вы можете использовать поиск по интерполяции в журнале регистрации времени n, если ваши номера нормально распределены. Если у них есть какой-то другой дистрибутив, вы можете изменить его, чтобы учесть ваш дистрибутив, хотя я не знаю, какие дистрибутивы дают время записи журнала.