Пусть дан массив
a длины
n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента
x в массиве
a длины
n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:
. . . // Утверждение: a[0] < x && x <= a[n-1] int beg = 0; int end = n-1; while (end-beg > 1) { // Инвариант: a[beg] < x && x <= a[end] int c = (beg + end) / 2; if (a[c] < x) { beg = c; } else if (a[c] > x) { end = c; } else { // Утверждение: x == a[c] *idx = c; return true; } } *idx = end; return (x >= a[end]); . . .
Пусть значение
x содержится в массивев нескольких экземплярах. Индекс какого элементамассива
a будет записан в переменную
*idx?