WHILE L<R DO

BEGIN

j: = (L + R) DIV 2;

IF a [j] < x THEN L: = j + 1 ELSE R: = j;

END;

IF a [R] = x THEN writeln(‘ искомый элемент ‘, a [R]);

Условие окончания - L ≥ R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при и всех обстоятельствах разность R – L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L ≤ m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m + 1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N + 1 никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а [R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а [R] = х. В отличие от первого нашего решения (5.5) приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.

· МОДУЛЬ 3. СОРТИРОВКА

· ТЕМА 1. ВНУТРЕННЯЯ И ВНЕШНЯЯ СОРТИРОВКИ

В этой части мы будем обсуждать методы сортировки информации. В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения («=», «>», «<», «> =» и «< =»). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам (т.е. свойствам), не влияющим на основной ключ.

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

1. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

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

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

· ТЕМА 2. МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ

Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).

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

Методы сортировки «на том же месте» можно разбить в соответствии с определяющими их принципами на три основные категории:

1. Сортировки с помощью включения (by insertion).

2. Сортировки с помощью выбора (by selection).

3. Сортировки с помощью обменов (by exchange).