Цикл инвариант линейного поиска

Как видно из Введения в алгоритмы (http://mitpress.mit.edu/algorithms), в упражнении говорится следующее:

Вход: Массив A[1...n]

Вывод: i, где A[i]=v или NIL, когда не найден

Напишите псевдокод для ЛИНЕЙНОГО ПОИСКА, который сканирует последовательность, ищу в. Используя инвариант цикла, докажите, что ваш алгоритм верен. (Убедитесь, что цикл инвариантный выполняет три необходимых свойства – инициализация, сопровождение, прекращение.)

У меня нет проблем с созданием алгоритма, но чего я не понимаю, так это того, как я могу решить, что является инвариантом моего цикла. Думаю, я понял понятие инварианта цикла, то есть условия, которое всегда истинно перед началом цикла, в конце/начале каждой итерации и по-прежнему true, когда цикл заканчивается. Обычно это цель, поэтому, например, при сортировке вставки, itearting over j, начиная с j=2, всегда сортируются элементы [1, j-1]. Для меня это имеет смысл. Но для линейного поиска? Я не могу ничего придумать, просто это звучит слишком просто, чтобы думать об инварианте цикла. Я понял что-то не так? Я могу думать только о чем-то очевидном вроде (это либо NIL, либо между 0 и n). Заранее большое спасибо!