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

1 minute read

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

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

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

Путь также - левая граница поиска (т.е. ), а - правая граница поиска ().

Положим , и если - обновим левую границу , в противном случаев обновим правую границу . Продолжая, в конечном итоге получим, что . Тогда в в конце работы алгоритма будет содержаться либо номер самого первого вхождения в , либо номер первого числа, строго большего , если самого числа нет в массиве.

Пример реализации на языке 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

Leave a Comment

Your email address will not be published. Required fields are marked *

Loading...