Практическая работа Инвариант цикла Определите инвариант цикла для следующего алгоритма двоичного поиска

Инвариант цикла - это условие или свойство, которое выполняется на каждой итерации цикла и сохраняется неизменным до его завершения. Давайте разберемся с заданием и найдем инвариант цикла для данного алгоритма двоичного поиска.

На картинке представлен алгоритм двоичного поиска. Этот алгоритм ищет значение `x` в отсортированном массиве `arr`. Переменная `L` содержит нижнюю границу поиска, `R` - верхнюю границу, а `M` - середину секции, в которой ищется значение `x`.

1. Начнем с определения инварианта цикла в данном алгоритме. Что-то, что будет сохраняться неизменным на каждой итерации цикла.
2. Обратим внимание на условие цикла while. Цикл выполняется, пока `L` не станет больше `R`. Это означает, что поиск продолжается, пока нижняя граница не станет больше верхней границы.
3. Предположим, что на каждой итерации цикла инвариант цикла будет состоять в том, что искомое значение `x` находится в секции массива `arr[L:R+1]`. Другими словами, `x` находится между элементами `arr[L]` и `arr[R]`, включая эти элементы.
4. Обоснуем и проверим данное предположение.
- На первой итерации цикла `L = 0` и `R = len(arr)-1`, поэтому инвариант цикла будет верным, так как `x` может находиться в любом месте от `arr[0]` до `arr[len(arr)-1]`.
- На каждой последующей итерации цикла мы сравниваем `x` с серединным элементом `arr[M]`, где `M = (L + R) // 2` (целочисленное деление). Если `x` меньше `arr[M]`, то мы переносим верхнюю границу поиска `R` на `M - 1`, так как `x` должен находиться в левой половине секции `arr[L:R+1]` (если `x` вообще находится в этой секции). Если `x` больше `arr[M]`, то мы переносим нижнюю границу поиска `L` на `M + 1`, так как `x` должен находиться в правой половине секции `arr[L:R+1]` (если `x` вообще находится в этой секции).
- Заметьте, что на каждой итерации цикла мы сужаем границы поиска, так как `L` увеличивается или `R` уменьшается. Но при этом инвариант цикла остается верным, так как мы всегда ищем `x` в текущей секции.
- Когда цикл заканчивается и `L > R`, это означает, что `x` не найдено в массиве `arr`. В таком случае, инвариант цикла равен ложному утверждению.

Таким образом, можно сказать, что инвариант цикла для данного алгоритма двоичного поиска состоит в том, что искомое значение `x` находится в секции массива `arr[L:R+1]` на каждой итерации цикла, где `L` и `R` - текущие границы поиска. Когда цикл завершается и `L > R`, значит, значения `x` в массиве нет.