Классические алгоритмы, известные еще в середине семидесятых годов, не утратили своего значения и по сей день. Эти алгоритмы помогут вам сделать программы быстрыми и красивыми и послужат хорошей школой программирования. К несчастью, в последнее время появляется все больше "программистов", способных написать базу данных на Visual Basic, но не представляющих себе, что такое рекурсия или быстрая сортировка. Конечно, во многих средах программирования теперь не надо явно задавать алгоритмы поиска или сортировки - это уже сделано за вас командой разработчиков, и вам остается только вызывать соответствующие команды. Но если вы не представляете, что при этом происходит, ваши программы никогда не достигнут максимальной эффективности.

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

А начнем мы рассмотрение классических алгоритмов с алгоритма бинарного поиска. Постановка задачи поиска в нашем случае будет звучать так: имеется массив, содержащий набор однотипных значений (например, записей, содержащих информацию о сотрудниках). Задается некоторый ключ (например, фамилия). Требуется определить номер записи, содержащей ключ.

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

Для единообразия будем считать, что элементы упорядочены по возрастанию. Такой массив имеет замечательное, хоть и вполне очевидное, свойство - если выбрать в нем произвольный пробный элемент, то все элементы с большим, чем у пробного, значением ключа будут иметь в нем большие номера, с меньшим - меньшие. На этом и основан алгоритм бинарного поиска.

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

1. Положить началом рабочей области начало массива, концом - его конец.

2. Выбрать в качестве пробного элемент точно в середине рабочей области.

3. Если значение ключа пробного элемента равно искомому, то поиск закончен.

4. Если значение ключа пробного элемента меньше, чем искомое, то взять номер пробного элемента в качестве начала рабочей области.

5. Если значение ключа пробного элемента больше, чем искомое, то взять номер пробного элемента в качестве конца рабочей области.

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

Как видим, размер рабочей области за каждый прогон алгоритма сокращается вдвое (поэтому-то поиск и назван бинарным), что гораздо эффективнее, чем последовательный просмотр, который сокращает рабочую область на один элемент за один ход. Далее приведу фрагмент паскалевского кода, реализующего алгоритм.

В этом фрагменте St и En - начало и конец рабочей области, try - значение ключа искомого элемента, a - массив записей, в котором осуществляется поиск (структура самих записей в данном случае не важна), Key - имя поля-ключа, i - индекс пробного элемента.

Следует обратить пристальное внимание на то, каким образом рассчитываются начало и конец рабочей области для нового шага алгоритма. Особый интерес представляет из себя добавка (En-St) mod 2 в конце формулы перенесения конца рабочей области в пятой строке листинга. Убедитесь, что без нее программа работает неверно и попытайтесь понять, для чего она нужна.

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

Пусть требуется возвести число в целую степень. В самом примитивном варианте его можно просто умножить само на себя нужное количество раз, но это - самый медленный из способов. Мы же воспользуемся следующей идеей.

1. Если степень, в которую нужно возвести число, четная, то возведем его в квадрат, а квадрат - в степень вдвое меньше первоначальной.

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

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

В заключение хочется предложить читателю подумать над тем, какие еще задачи могут быть упрощены при помощи приведенной в статье методики: поверьте, деление на два - один из фундаментальнейших алгоритмов, он помогает в решении огромного количества задач.

Денис МАРГОЛИН,
margolindenis@usa.net

while (St<>En) and (a[i].Key<>try) do
 begin
 i:=St+(En-St) div 2;
 if a[i].Key<try then St:="St+(En-St)" div 2 else if a[i].Key>try
 then En:=En-(En-St) div 2-(En-St) mod 2;
 end;
if a[i].Key=try
 then writeln(i)
 else writeln('not found');