1. введение
В этом уроке мы рассмотрим алгоритмы интерполяционного поиска и обсудим их плюсы и минусы. Кроме того, мы реализуем его на Java и поговорим о сложности алгоритмов по времени.
2. Мотивация
Интерполяционный поиск является улучшением по сравнению с двоичный поиск специально для равномерно распределенных данных.
Двоичный поиск делит пространство поиска пополам на каждом шаге независимо от распределения данных, поэтому временная сложность всегда O(log(n)) .
С другой стороны, сложность интерполяционного поиска варьируется в зависимости от распределения данных . Это быстрее, чем двоичный поиск равномерно распределенных данных с временной сложностью O(log(log(n))) . Однако в худшем случае он может работать так же плохо, как O(n) .
3. Интерполяционный поиск
Как и двоичный поиск, интерполяционный поиск может работать только с отсортированным массивом. Он помещает зонд в расчетное положение на каждой итерации. Если зонд находится прямо на искомом элементе, позиция будет возвращена; в противном случае пространство поиска будет ограничено либо правой, либо левой стороной зонда.
Вычисление положения зонда-это единственное различие между двоичным поиском и интерполяционным поиском.
При двоичном поиске позиция зонда всегда является самым средним элементом оставшегося пространства поиска.
Напротив, интерполяционный поиск вычисляет положение зонда на основе этой формулы:
Давайте рассмотрим каждый из терминов:
- зонд : этому параметру будет присвоено новое положение зонда.
- нижний конец : индекс самого левого элемента в текущем пространстве поиска.
- high End : индекс самого правого элемента в текущем пространстве поиска.
- data[] : массив, содержащий исходное пространство поиска.
- пункт : пункт, который мы ищем.
Чтобы лучше понять, как работает интерполяционный поиск, давайте продемонстрируем это на примере.
Допустим, мы хотим найти позицию 84 в приведенном ниже массиве:
Длина массива равна 8, поэтому изначально high End = 7 и low End = 0 (поскольку индекс массива начинается с 0, а не с 1).
На первом этапе формула положения зонда приведет к зонд :
Поскольку 84 (искомый элемент item ) больше 73 (текущий элемент probe position), следующий шаг откажется от левой части массива, назначив lowEnd = probe + 1. Теперь пространство поиска состоит только из 84 и 101. Формула probe position установит probe = 6, что в точности соответствует индексу 84:
Поскольку предмет, который мы искали, найден, позиция 6 будет возвращена.
4. Реализация на Java
4. Реализация на Java
Сначала мы инициализируем lowEnd и HighEnd :
int highEnd = (data.length - 1); int lowEnd = 0;
Затем мы настраиваем цикл и на каждой итерации вычисляем новый зонд на основе вышеупомянутой формулы. Условие цикла гарантирует, что мы не выберемся из пространства поиска, сравнивая item с data[low End] и data[high End] :
while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) {
int probe
= lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]);
}Мы также проверяем, нашли ли мы предмет после каждого нового пробного задания.
Наконец, мы настраиваем low End или high End , чтобы уменьшить пространство поиска на каждой итерации:
public int interpolationSearch(int[] data, int item) {
int highEnd = (data.length - 1);
int lowEnd = 0;
while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) {
int probe
= lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]);
if (highEnd == lowEnd) {
if (data[lowEnd] == item) {
return lowEnd;
} else {
return -1;
}
}
if (data[probe] == item) {
return probe;
}
if (data[probe] < item) {
lowEnd = probe + 1;
} else {
highEnd = probe - 1;
}
}
return -1;
}5. Заключение
В этой статье мы рассмотрели интерполяционный поиск на примере. Мы также реализовали его на Java.
Примеры, показанные в этом руководстве, доступны на Github .