Пусть дан массив
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 { end = c; } } if (a[beg] == x) { *idx = beg; } else { *idx = end; } . . .
Пусть значение
x содержится в массивев нескольких экземплярах. Индекс какого элементамассива
a будет записан в переменную
*idx?