Peter Almazov писал(а):
Не по памяти, а синтезировать программу используя маразм (зачеркнуто) "шаблон" линейный поиск. Иначе зачем базарить про него?
Приведено как начальный вариант в новой редакции АСД:
Код:
L := 0; R := N -1;
m := любое значение между L и R;
WHILE (L <= R) & (a[m] # x) DO
IF a[m] < x THEN
L := m + 1
ELSE
R := m - 1
END;
m := любое значение между L и R
END
Цитата:
Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R. Чтобы не потерять это подобие и тем самым надёжнее гарантировать корректность цикла, мы воздержались от соблазна мелкой оптимизации программы с целью устранения дублирование инструкции присваивания переменной m.
<Дальше инвариант (A k: 0 <= k < L: a_k < x) & (A k: R < k < N: a_k > x)
и обоснование корректности>
Как уже упоминалось, можно заняться устранением дублирования инструкции присваивания m. Однако такая оптимизация на уровне кода является преждевременной в том смысле, что сначала лучше попытаться оптимизировать алгоритм на уровне логики задачи. Здесь это действительно возможно: ввиду сходства алгоритма с алгоритмом линейного поиска естественно искать решение с более простым условием окончания, то есть без второго операнда конъюнкции в охране цикла (И.Е.: аналогия с барьером в случае ЛП). Для этого нужно отказаться от наивного желания закончить поиск сразу после нахождения искомого значения. На первый взгляд это неразумно, но при ближайшем рассмотрении оказывается, что выигрыш в эффективности на каждом шаге больше, чем...
Более быстрое решение основано на следующем инварианте:
(A k: 0 <= k < L : a_k < x) & (A k: R <= k < N : a_k >= x), а поиск продолжается, пока два отрезка не будут покрывать весь массив.
Код:
L := 0; R := N;
WHILE L < R DO
m := (L + R) DIV 2;
IF a[m] < x THEN L := m + l ELSE R := m END
END
Цитата:
Можно сказать, что теперь ищется не элемент a[m] = x, а граница, отделяющая все элементы, меньшие x, от всех прочих.
... В отличие от первого решения, данный алгоритм - как и линейный поиск - находит искомое значение в позиции с наименьшим индексом.