Как видно из введения к алгоритмам (http://mitpress.mit.edu/algorithms), упражнение гласит следующее:
Вход: массив A [1... n]
Выход: i, где A [i] = v или NIL, если не найден
Напишите псевдокод для LINEAR-SEARCH, который сканирует последовательность, ищет v. Используя инвариант цикла, убедитесь, что ваш алгоритм верен. (Убедитесь, что ваш цикл инвариант выполняет три необходимых свойства - инициализация, обслуживание, прекращение.)
У меня нет проблем с созданием алгоритма, но я не понимаю, как я могу решить, что мой цикл является инвариантным. Я думаю, что я понял концепцию циклического инварианта, то есть условие, которое всегда истинно до начала цикла, в конце/начале каждой итерации и все еще верно, когда цикл завершается. Обычно это цель, например, при сортировке вставки, начинающейся с j, начиная с j = 2, элементы [1, j-1] всегда сортируются. Это имеет смысл для меня. Но для линейного поиска? Я ничего не могу придумать, просто звучит слишком просто, чтобы думать о циклическом инварианте. Я что-то понял неправильно? Я могу только думать о чем-то очевидном (это либо NIL, либо между 0 и n). Большое спасибо заранее!