Строковые данные (Подробнее – в кн. Н. Вирта "Алгоритмы и структуры данных")
Если данные в списке представляют собой строки, можно применить два различных подхода. Более простой состоит в применении двоичного поиска. При двоичном поиске значения элементов сравниваются непосредственно, поэтому этот метод может легко работать со строковыми данными.
С другой стороны, интерполяционный поиск использует численные значения элементов данных для вычисления возможного положения искомого элемента в списке. Если элементы представляют собой строки, то этот алгоритм не может непосредственно использовать значения данных для вычисления предполагаемого положения искомого элемента.
Если строки достаточно короткие, то можно закодировать их при помощи целых чисел или чисел формата longилиdouble. После этого можно использовать для нахождения элементов в списке интерполяционный поиск.
Если строки слишком длинные, и их нельзя закодировать даже числами в формате double, то все еще можно использовать для интерполяции значения строк. Вначале найдем первый отличающийся символ для строкList(min)иList(max). Затем можно использовать эти значения для выполнения интерполяционного поиска.
Например, предположим, что мы ищем строку TARGETв спискеTABULATE,TANTRUM,TARGET,TATTERED,TAXATION. Еслиmin = 1иmax = 5, то проверяются значенияTABULATEиTHEATER. Эти строки отличаются во втором символе, поэтому нужно рассматривать три символа, начинающиеся со второго. Это будут символыABUдляList(1),AXAдляList(5)иARGдля искомой строки.
Эти значения кодируются числами 804, 1378 и 1222 соответственно. Подставляя эти значения в формулу для переменной middle, получим:
middle = min + (target - List(min)) * ((max - min) / (List(max) - List(min)))
= 1 + (1222 – 804) * ((5 – 1) / (1378 – 804))
= 2,91
Это примерно равно 3, поэтому следующее значение переменной middleравно 3. Это положение строкиTARGETв списке, поэтому поиск при этом заканчивается.
Следящий поиск
Чтобы начать двоичный следящий поиск (binaryhuntandsearch), сравним искомое значение из предыдущего поиска с новым искомым значением. Если новое значение меньше, начнем слежение влево, если больше — вправо.
Для выполнения слежения влево, установим значения переменных minиmaxравными индексу, полученному во время предыдущего поиска. Затем уменьшим значениеminна единицу и сравним искомое значение со значением элементаList(min). Если искомое значение меньше, чем значениеList(min), установимmax = minиmin = min –2, и сделаем еще одну проверку. Если искомое значение все еще меньше, установимmax = minиmin = min –4, если это не поможет, установимmax = minиmin = min –8и так далее. Продолжим устанавливать значение переменнойmaxравным значению переменнойminи вычитать очередные степени двойки из значения переменнойminдо тех пор, пока не найдется значениеmin, для которого значение элементаList(min)будем меньше искомого значения.
Необходимо следить за тем, чтобы не выйти за границы массива, если minменьше, чем нижняя граница массива. Если в какой-то момент это окажется так, тоminнужно присвоить значение нижней границы массива. Если при этом значение элементаList(min)все еще больше искомого, значит искомого элемента нет в списке. Слежение вправо выполняется аналогично. Вначале значения переменныхminиmaxустанавливаются равными значению индекса, полученного во время предыдущего поиска. Затем последовательно устанавливаетсяmin = maxиmax = max + 1,min = maxиmax = max + 2,min = maxиmax = max + 4, и так далее до тех пор, пока в какой-то точке значение элемента массиваList(max)не станет больше искомого. И снова необходимо следить за тем, чтобы не выйти за границу массива.
После завершения фазы слежения известно, что индекс искомого элемента находится между minиmax. После этого можно использовать обычный двоичный поиск для нахождения точного положения искомого элемента.
Если новый искомый элемент находится недалеко от предыдущего, то алгоритм следящего поиска очень быстро найдет значения maxиmin. Если новый и старый искомые элементы отстоят друг от друга наPпозиций, то потребуется порядкаlog(P) шагов для следящего поиска новых значений переменныхminиmax.
Предположим, что мы начали обычный двоичный поиск без фазы слежения. Тогда потребуется порядка log(NumItems) –log(P) шагов для того, чтобы значенияminиmaxбыли на расстоянии не больше, чемPпозиций друг от друга. Это означает, что следящий поиск будет быстрее обычного двоичного поиска, еслиlog(P) <log(NumItems) –log(P). Прибавив к обеим частям уравненияlog(P), получим 2 *log(P) >log(NumItems). Если возвести обе части уравнения в степень двойки, получим 22*log(P)< 2log(NumItems)или (2log(P))2<NumItems, или после упрощенияP2<NumItems.
Из этого соотношения видно, что следящий поиск будет выполняться быстрее, если расстояние между последовательными искомыми элементами будет меньше, чем квадратный корень из числа элементов в списке. Если следующие друг за другом искомые элементы расположены далеко друг от друга, то лучше использовать обычный двоичный поиск.