Пусть элементы массива aнестрого возрастают (соседние элементы могут быть равными).Дано произвольное значение x, требуетсянайти максимальный индекс i такой, чтоa[i] <= x. Используется идея алгоритмабинарного поиска. В приведенном ниже циклерассматривается основной случай после отбрасыванияисключительных ситуаций: while (end-beg > 1) { int c = (beg+end)/2; if (a[c] <= x) beg = c; else end = c; } // ответ в переменной beg
Какое утверждение являетсяинвариантом этого цикла?
(Отметьте один правильный вариант ответа.)
Варианты ответа
a[beg] < x <= a[end].
a[beg] > x <= a[end].
a[beg] < x >= a[end].
a[beg] <= x < a[end]. (Верный ответ)