Строковые данные

Если данные в списке представляют собой строки, можно применить два различных подхода. Более простой состоит в применении двоичного поиска. При двоичном поиске значения элементов сравниваются непосредственно, поэтому этот метод может легко работать со строковыми данными.

С другой стороны, интерполяционный поиск использует численные значения элементов данных для вычисления возможного положения искомого элемента в списке. Если элементы представляют собой строки, то этот алгоритм не может непосредственно использовать значения данных для вычисления предполагаемого положения искомого элемента.

Если строки достаточно короткие, то можно закодировать их при помощи целых чисел или чисел формата long или double, используя методы, которые были описаны в 9 главе. После этого можно использовать для нахождения элементов в списке интерполяционный поиск.

Если строки слишком длинные, и их нельзя закодировать даже числами в формате double, то все еще можно использовать для интерполяции значения строк. Вначале найдем первый отличающийся символ для строк List(min) и List(max). Затем закодируем его и следующие два символа в каждой строке при помощи методов из 9 главы. Затем можно использовать эти значения для выполнения интерполяционного поиска.

Например, предположим, что мы ищем строку 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

=========275

Это примерно равно 3, поэтому следующее значение переменной middle равно 3. Это положение строки TARGET в списке, поэтому поиск при этом заканчивается.

Следящий поиск

Чтобы начать двоичный следящий поиск (binary hunt and search), сравним искомое значение из предыдущего поиска с новым искомым значением. Если новое значение меньше, начнем слежение влево, если больше — вправо.

Для выполнения слежения влево, установим значения переменных 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) все еще больше искомого, значит искомого элемента нет в списке. На рис. 10.4 показан следящий поиск элемента со значением 17 влево от предыдущего искомого элемента со значением 44.

Слежение вправо выполняется аналогично. Вначале значения переменных min и max устанавливаются равными значению индекса, полученного во время предыдущего поиска. Затем последовательно устанавливается min = max и max = max + 1, min = max и max = max + 2, min = max и max = max + 4, и так далее до тех пор, пока в какой‑то точке значение элемента массива List(max) не станет больше искомого. И снова необходимо следить за тем, чтобы не выйти за границу массива.

После завершения фазы слежения известно, что индекс искомого элемента находится между min и max. После этого можно использовать обычный двоичный поиск для нахождения точного положения искомого элемента.

@Рис. 10.4. Следящий поиск значения 17 из значения 44

===============276

Если новый искомый элемент находится недалеко от предыдущего, то алгоритм следящего поиска очень быстро найдет значения 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). Если возвести обе части уравнения в степень двойки, получим 2^2*log(P) < 2^{log(NumItems)} или (2^log(P))² < NumItems, или после упрощения P² < NumItems.

Из этого соотношения видно, что следящий поиск будет выполняться быстрее, если расстояние между последовательными искомыми элементами будет меньше, чем квадратный корень из числа элементов в списке. Если следующие друг за другом искомые элементы расположены далеко друг от друга, то лучше использовать обычный двоичный поиск.