== Код ==
Далее будет привед код, который будет возвращать пару, соттвтственно левую и правую границы вхождения нашего элемента. Индексация в массиве начинается с <tex>0</tex>.<pre>
pair<int, int> binsearch (vector<int> & a, int k) { int x = -1, y = -1; //левый и правый индекс вхождения if (a[0] > k) { //проверка на существование элемента return {x, y}; } int l = 0;
// l - левая граница
int r =
a.size()n + 1;
// r - правая граница
while
(l < r
) { - 1 // запускаем цикл
int m =
(l +
(r
- l) / 2;
// m - середина области поиска if
(k <= a[m]) r = m; else l = m + 1; } if (a[r] == k) { x = r; } l = 0; r = a.size(); while (r - l > 1) { int m = l + (r - l) / 2; if (a[m] <
= k
) l = m;
else
r = m; // сужение границ } if (a[lr] == k) y result = lr; // выводим найденный индекс return {x, y} else result = -1;} // если элемент не найден возвращаем -1
</pre>
В случае правостороннего поиска изменится знак сравнения при сужении границ на (a[m] <= k), также при выводе найденного индекса, мы сравниваем искомый элемент k с a[l].
Инвариант цикла: l <= r && «если k == a[k], то l <= k <= r»
