Изменения

'''Целочисленный двоичный поиск (бин. поиск)''' - алгоритм поиска аргумента для заданного значения монотонной целочисленной функцииобъекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку.

Пусть нам дана монотонная функциядан упорядоченный массив, значения которой целые числасостоящий только из счетных элементов. Нам необходимо надо найти местов нем индекс, где функция будет равна заданному значениюпо которому находиться искомый элемент. Или же мы можем находить интервалы вхождения искомого элемента. Для этой задачи мы и можем использовать двоичный поиск.

== Выбор границы Принцип работы==Нам должны быть заданы границыДвоичный поиск заключается в том, что на которых каждом шаге множество объектов делится на две части и в работе остается та часть множества, где находится искомый объект. Или же, в зависимости от постоновки задачи, мы можем остановить процесс, когда мы ищем получим первый или же последний индекс заданного значения <b>х<вхождения элемента. Последнее условие - это левосторонний/b>правосторонний двоичный поиск.

[[Файл:schemeshcemebinsearch.jpgpng|350px|thumb|right|Схема бин. поиска]]<br>

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