Изменения

'''Целочисленный двоичный поиск (бин. поиск)<i>(от англ. Binary Search)</i>''' {{---}} алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку.

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

Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остается остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие {{---}} это левосторонний/правосторонний двоичный поиск.

Когда мы ищем правосторонним бин. бинарным поиском, то он возвращает индекс самого правого вхождения заданного значения <tex> x </tex> .

<pre>binSearch(l, r) // l, r - левая и правая границы while l < r - 1 // запускаем цикл m = (l + r) / 2; // m - середина области поиска if a[m] < k l = m; else r = m; // сужение границ