Бинарный поиск

Реализация двоичного поиска.

Будем считать, что поиск происходит по массиву целых чисел $A$, элементы которого расположены в порядке возрастания.

Пусть $x$ - искомое число.

Путь также $left$ - левая граница поиска (т.е. $A[left] < x$), а $right$ - правая граница поиска ($A[right] >= x$).

Положим $m = (left + right) / 2$, и если $A[m] < x$ - обновим левую границу $left$, в противном случаев обновим правую границу $right$. Продолжая, в конечном итоге получим, что $left = right - 1$. Тогда в $right$ в конце работы алгоритма будет содержаться либо номер самого первого вхождения $x$ в $A$, либо номер первого числа, строго большего $x$, если самого числа $x$ нет в массиве.

Пример реализации на языке Python:

A = [1, 2, 4, 5, 7, 9, 10, 12, 15]
x = 8
left = -1
right = len(A)
while right - left > 1:
    m = (left + right) // 2
    if A[m] < x:
        left = m
    else:
        right = m
print(right) # 5

Пример реализации на языке C++:

 // Требуется 11 стандарт для такого способа задания массива
vector<int> A = {1, 2, 4, 5, 7, 9, 10, 12, 15};
int x = 8;
int left = -1;
int right = A.size();
while (right - left > 1) {
    int m = (left + right) / 2;
    if (A[m] < x)
        left = m;
    else
        right = m;
}
cout << right << endl; // 5