Инвариант это просто топ слово. А значит оно ровно вот что - постоянное, неизменное Скажешь "сохраняется инвариант" на собеседовании, и сразу +10 очков за стиль, только не забудь, что после этой фразы должно быть что-то осмысленное, дальше объясню Фразы в копилочку: - внутренний/внешний цикл (второй содержит первый) - в начале каждой итерации цикла/функции (это про начальные условия, это база, видишь аналогии? в добавок это ключ к построению инварианта) - в конце каждой итерации цикла (это уже про инвариант, и больше похоже на шаг в математической индукции) - после цикла - результат последней итерации цикла (зная инвариант все становится просто) А вообще, зачем это все: - приятно быть на одной волне, используя одинаковые термины, уметь подсветить кусочек, который тебе кажется важным - "сохраняется инвариант" звучит даже лучше, чем "легко увидеть" - обычно после того, как вы вместе увидели, что сохраняется какой-то инвариант, задача решена и все аплодируют - очень полезно самому искать инварианты в своем коде и проговаривать про себя их, потому что обычно "является" или "не является" ли какое-от утверждение инвариантом влияет вообще на все И так, что я имею в виду под инвариантами: - Простое. В конце каждой итерации цикла в переменной sum хранится сумма всех чисел от 1 до i включительно sum = 0 for i in range(1, N + 1): sum += i - Сложнее, пришлось покодить минут 20 чтобы правильно сформулировать. Для бинарного поиска нужно несколько инвариантов - в начале каждой итерации цикла у нас расстояние между left и right как минимум 2 - следовательно, у нас есть элемент между left и right - следовательно, mid не равен ни left, ни right (сложнее увидеть, проще проверить, но в качестве упражнения можно и доказать) - следовательно left и right все время сближаются, а это не позволяет нам зациклиться - если у в начале цикла у нас в [left, right) содержался один или несколько элементов равных x, то и в конце цикла в (обновленном) интервале [left, right) содержится самый правый элемент, который был равен x - после цикла у нас либо один элемент в оставшемся полуинтервале, либо ноль, в зависимости от того, чему оставшийся элемент равен, если он есть, зависит ответ def bin_search(arr, x): left, right = 0, len(arr) while right - left > 1: mid = (left + right) // 2 if arr[mid] <= x: left = mid else: right = mid if left == right or arr[left] > x: return left return left + 1 Если не знаешь, что такое бинарный поиск - не беда, погугли или подожди одну из следующих пятиминуток #пятиминутка #математика #python