ВЫВОД ШАБЛОНА БИНАРНОГО ПОИСКА.

1 к 1 ix к

A >> <>x =x <x =x

X или 1 x

<>x <x >x

Идея алгоритма: проверим элемент в середине массива, если окажется что он >x, то гарантированно, что все элементы правее него тоже >, если меньше, то тоже меньше , если равен, то надо продолжать поиск слева. Т.о. каждое сравнение уменьшает область поиска вдвое.

Допустим к=1000, тогда линейный поиск потребует от 1 до 1000 сравнений. А бинарный поиск всего 10. Если к=1000000, то – 20.

Второй прием формулировки инварианта.

Выполним вручную несколько шагов цикла и нарисуем картинку в том промежуточном состоянии.

>x >x

>x

Очевидно, что если бы при первом сравнении вместо >x оказалось =x то потребовалось тоже самое действие: исследование левой половины. Притом, о правой половине мы знаем уже то, что там >x, а что >=x необходимо рассмотреть два случая <x и >=x

>=x >=x Это и есть инвариант

Nл Nп

<x <x >=x (I)

Nл=1 Nл Nп

Nп=к ^{1 N}

Повторяй пока Nл<=Nп _{Nл Nп}

I <x >=x

_{Nл Nc Nп}

NC=(Nл+Nп)/2 <x >=x

Если A(NC)<x

Nл=NC+1 < < >=

Иначе

Nл=NC-1 < >= >=

Nл>Nп <x >=x

В конце необходимо выяснить какая из двух целевых ситуаций произошла. Достаточно повторить равен ли x элемент справа от слившейся границы т.е. элемент с номером Nп. Если A(Nп)=x

Если A(Nп)=0

Msgbox "x в N" & Nл

Msgbox "x нет в A"

В описанном шаблоне имеется ошибка. Задание: найти рассмотреть случай когда все A <x

Ошибка: ошибка в алгоритме (алгоритм бинарного поиска) проявляется в том случае, когда все A меньше x.

^{Nп Nл}

<x

Поскольку после цикла делается проверка A(Nл)=x. В описанной ситуации произойдет ошибка «выход индекса за границу массива».

Рассмотрим слегка модифицированный инвариант:

(1) (2)

A <x >x или x не принадлежит A

→ ←

Тогда в начальном состоянии как обычно надо добиться истинности инварианта.

Рассмотрим отдельно два случая:

1. Допустим x нет в A, тогда (2) гарантированно истинно, инвариант тоже истинен.

2. Пусть x есть в A тогда (2) ложно и нам необходимо сделать истинным (1).

Это аналогично ситуации с исходным немодифицированным инвариантом с одним отличием: надо учесть что в (1) x есть в A. При этом в A гарантированно есть хотя бы один элемент >=x. То в начальном состоянии инвариант выглядит так:

_{Nл Nп к}

ИЛИ x не принадлежит A

Потому начальные присваивания:

Nл=1

Nп=к-1

Более никаких изменений в алгоритме не потребуется.

К инварианту в промежуточном и конечном состоянии добавится «или x не принадлежит A».

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

Рассмотрим работу условного оператора после цыкла.

В случае если x есть в A состояние после цикла описывается условием:

_{Nп Nл} (I) (II)

<x >=x или x не принадлежит A

Поскольку мы предположили, что x не принадлежит A, то (II) ложно, т.е. истинно (I). Отсюда следует, что A(Nл) должен быть равен x.

Пусть x нет в A, тогда условие (II) верно, но известно, что Nл<=к.

Поскольку все элементы A неравны x, то A(Nл) тоже гарантированно не равен x. Таким образом, теперь проверку A(Nл)=x можно безопасно использовать, как синоним проверки «x есть в A».

ВЫВОД ШАБЛОНА MIN.

_{1 к к}

A >>

_m=min

Инвариант – промежуточное состояние. Формулируем его: вначале мы минимум не знаем, в конце – знаем минимум по всем элементам. Значит, в промежуточном состоянии знаем минимум только по части элементов. Инвариант: Минимум известен не по всем элементам, а по части. Отделим эту часть границей (считаем, что знаем минимум по левой из частей). Обозначим известный минимум по этой части через m. Чтобы ситуация улучшалась просмотренная часть должна увеличиваться, т.е. граница должна сдвигаться вправо. Чтобы запомнить положение границы надо запомнить номер элемента слева или справа от нее. Запоминать будет исполнитель, а для программиста необходимо обозначить его. Назовем его Nп – номер проверяемого.

Nп=2 m=A(1)

повторяй пока

если A(Nп)<A

m=A(Nп)

Nп=Nп+1 ‘Nп>к