идно на Введение в алгоритмы (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). Заранее большое спасибо!