Валерий Лаптев писал(а): Препод я тоже самоучка, и стал преподавать только после 40. Года этак с 95-го, стал задумываться, а как, собственно, учить программированию... И практически ничего, кроме словесов, найти не мог. Пока вот на этот оберонский форум не наткнулся... Ну вот вам пример с двоичным поиском.
Как решать эту задачу? Первым делом здесь, как и в 100% других случаев, нужно попытаться сформулировать инвариант цикла. Здесь как раз потребуется и опыт, и догадка, и интуиция. Например, Бентли ([1] c. 51) приводит такой инвариант: "если элемент T вообще есть в массиве X[1..N], то он должен быть в некоторой области, принадлежащей X". Первоначально эта область – весь массив. Уже по слову "если" в этой формулировке видно, насколько она корявая. Думаю, причина этого в том, что у Бентли мало опыта – он, как и многие, использует всю это теорию только для обучения, а не для реальной жизни.
Вот нормальный инвариант цикла: определим область, где НЕ содержится искомый элемент. Первоначально эта область состоит из двух несмежных кусков нулевой длины (толщины, если угодно) в начале и в конце массива. Она не содержит искомый элемент, т. к. пуста и вообще ничего не содержит. Если в процессе работы эта область покроет весь массив, то искомого элемента в массиве нет.
Формально (буквы и размерность массива 1..N как в [1]):
Aj: 1 <=j < L или U < j <= N: X[j] != T
Первоначально L=1, U=N, область пуста.
Когда область покроет весь массив? Когда L > U, достаточно L=U+1.
Предположим, средний элемент (обозначим его индекс как M) массива X не равен искомому элементу T. Как мы можем изменить L и U так, чтобы инвариант остался истинным? В такой постановке задача оказывается настолько простой, что здесь негде ошибиться. Если T больше среднего элемента, то во всем куске от 1 до среднего элемента нет T. Аналогично, если T меньше среднего элемента, то во всем куске от среднего элемента до N нет T. Область расширяется, в первом случае L:=M+1, во втором U:=M-1. Для полной наглядности можно нарисовать массив на бумаге в клеточку.
Вот и вся идея алгоритма, причем у нас есть уверенность, что мы нигде не ошиблись на плюс/минус 1.
При чем здесь "шаблон линейного поиска"? Правильно, ни при чем.
1. Бентли. Жемчужины творчества программистов. М:Радио и связь 1990.
|
