Как мы рассмотрели ранее, в главе 4, утверждения оказались весьма полезными при разработке алгоритма двоичного поиска. Они направляли нас при его написании и помогали доказать его корректность. Теперь мы попытаемся вставить их в код нашей программы, чтобы убедиться, что она выполняется именно так, как мы это себе представляли.
Для выражения уверенности в том, что некоторое утверждение является истинным, мы будем использовать оператор assert. Например, оператор assert(n>=0) не выполнит никаких действий, если п будет неотрицательно, по выдаст какое- либо сообщение об ошибке, если п окажется отрицательно (например, запустит отладчик). Перед тем как возвращать позицию найденного элемента, мы можем вставить соответствующее утверждение:
else if (х[m] == t) { as se^t(x[m] == t), return m.
} else
Это утверждение просто повторяет условие оператора if. Мы можем усилить утверждение, введя дополнительные требования, чтобы найденная позиция принадлежала исходному диапазону [0. .п-1]:
assert(0 <- m && m < п && x[m] == t).
При завершении цикла в том случае, когда искомый элемент отсутствует, мы знаем, что нижняя и верхняя границы I и и «пересеклись», и делаем вывод, что элемент в массиве отсутствует. Может возникнуть желание выразить это утверждение в форме, в которой оно будет означать, что мы нашли два соседних элемента, ограничивающих искомый:
assert(x[u]<t && x[u+l]>t),
return -1.
Логика тут в том, что если мы видим стоящие рядом в отсортированном масс и* ве элементы 1 и 3, то мы можем быть уверены, что элемента 2 в массиве нет. Однако это утверждение будет время от времени приводить к ошибке даже в правильной программе. Почему? |
Главная
Каталог файлов
