27. Двоичного поиска

Алгоритм двоичного поиска предполагает на каждом шаге деления массива на две части и отбрасывание той его части, элементы которой заведомо имеют значения либо меньше, либо больше искомого. Именно это повторяющееся деление на два послужило причиной того, что данный алгоритм был назван двоичным поиском. Псевдокод алгоритма приведен ниже. Входными параметрами алгоритма являются:Value - искомое значение; Array[] - массив элементов; FirstIndex - индекс начала фрагмента массива; LastIndex - индекс конца фрагмента массива.

function Search(Value, Array[], FirstIndex, LastIndex) {       MiddleIndex:= FirstIndex+(LastIndex-FirstIndex +1) div 2;       if (Value=Array[MiddleIndex]) then return MiddleIndex;       if (Value < Array[MiddleIndex]) then {            if (FirstIndex=MiddleIndex) then return Null;            Index:=Search(Value, Array[],FirstIndex, MiddleIndex-1);            if (Index <> Null) then return Index; else return Null;       }       if (Value > Array[MiddleIndex]) then {            if (MiddleIndex=LastIndex) then return Null;            Index:=Search(Value, Array[],MiddleIndex+1, LastIndex);            if (Index <> Null) then return Index; else return Null;       }  }

В приведенном выше псевдокоде последовательность символов divобозначает операцию целочисленного деления.

28. Базовые алгоритмические конструкции

Из приведенных блоков для нас представляют интерес логический блок и блок обработки информации. Именно они определяют логику работы алгоритма. Однако не следует произвольно соединять их между собой. При разработке программ рекомендуется разбивать общую задачу на отдельные подзадачи. Решение подзадачи представляет собой самостоятельный алгоритм, который может быть представлен как блок обработки информации с одним входом и одним выходом. Несоблюдение этого правила приводит к тому, что программа [алгоритм] становится плохо читаемой и запутанной. Правильно составленный алгоритм может быть собран из элементов четырех типов, которые будем называть базовыми алгоритмическими конструкциями. Каждая такая конструкция имеет по одному входу и выходу и может быть заменена одним блоком обработки.

Следование. Последовательность нескольких блоков обработки информации [см. рис. 1].

  Рис. 1. Следование

Ветвление. Эта конструкция состоит из логического блока и одно или двух блоков обработки информации [см. рис. 2]. Если блок обработки информации один, то говорят, что конструкция имеет сокращенную форму.

  Рис. 2. Ветвление

Цикл [повторение] с предусловием. Состоит из одного блока обработки информации и одного логического блока [см. рис. 3]. Команда выполняется до тех пор, пока условие не станет ложным.

  Рис. 3. Цикл с предусловием

Цикл [повторение] с постусловием. Существенное отличие от предыдущей конструкции заключается в том, что поскольку проверка условия находится в конце конструкции, то команда будет выполнена не менее одного раза [см. рис. 4].

Рис. 4. Цикл с постусловием

29. Итерационные и рекурсивные алгоритмы

Алгоритм, в состав которого входит цикл, называется итерационным [от лат. iteratio - повторение].

Алгоритм называется рекурсивным [от лат. recursio - возвращение], если обращение к этому алгоритму может производится из него самого.

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

На рис. 1 и 2 приведены блок-схемы соответственно итерационного и рекурсивного алгоритмов нахождения факториала.

  Рис. 1. Итерационный алгоритм

  Рис. 2. Рекурсивный алгоритм