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

Бинарный поиск элемента в отсортированном массиве

Рассмотрим задачу: дан массив a[], состоящий из целых чисел, и требуется найти в нём элемент x. Если x присутствует в a, то нужно вернуть его индекс (если x встречается несколько раз, то можно вернуть любой из подходящих индексов), иначе, если x нет, — вернуть -1.

Простейший способ решить такую задачу — пройти по всем элементам массива и сравнить их с x:

int search(int a[], int size, int x) { // ищем x в массиве a размера size
    for (int i = 0; i < size; i++)     // перебираем все элементы массива
        if (a[i] == x)                 // если элемент равен x,
            return i;                  // возвращаем его индекс
    return -1;                         // если не встретили x, возвращаем -1
}

Такое решение называют линейным поиском. Очевидно, что количество действий, которые данный алгоритм выполняет в худшем случае (когда x отсутствует в массиве), пропорционально размеру массива (поиск выполняется за O(N)).

Если массив отсортирован, то мы можем использовать более эффективную стратегию. Пусть массив упорядочен по возрастанию, тогда:

Найдём центральный элемент массива и сравним его с x. Если он равен x, то ответ найден;
Если центральный элемент меньше x, то искать ответ имеет смысл только в правой половине массива (так как слева все элементы тоже меньше x);
Если центральный элемент больше x, то искать ответ имеет смысл только в левой половине массива (так как справа все элементы тоже больше x);
При переходе в ту или иную половину мы снова определяем в ней средний элемент и сравниваем его с x, и так далее, пока ответ не будет найден или пока в рассматриваемой области не останется элементов.

Для того, чтобы отслеживать текущую область поиска, заведём индексы l и r. Будем считать, что поиск производится в отрезке от l до r включительно; таким образом, изначально l = 0, r = size - 1. Зная l и r, середину можно найти как (l + r) / 2 или l + (r - l) / 2.

int binarySearch(int a[], int size, int x) { // ищем x в отсортированном массиве a размера size
    int l = 0, r = size - 1;                 // ищем в отрезке [l; r]. изначально это весь массив
    while (l <= r) {                         // пока в отрезке поиска есть хотя бы один элемент,
        int m = l + (r - l) / 2;             // находим индекс среднего элемента отрезка
        if (a[m] == x)                       // если средний элемент равен x,
            return m;                        // возвращаем его индекс
        else if (a[m] < x)                   // если средний элемент меньше x,
            l = m + 1;                       // продолжаем искать в правой половине - [m + 1; r]
        else                                 // если средний элемент больше x,
            r = m - 1;                       // продолжаем искать в левой половине - [l; m - 1]
    }
    return -1                                // если не встретили x, возвращаем -1.
}

Такое решение называют бинарным поиском. Бинарный поиск гораздо быстрее линейного, так на каждой итерации он сокращает область поиска в два раза (поиск выполняется за O(logN)).

Число сравнений в худшем случае
Размер массива	Линейный поиск	Бинарный поиск
10	10	4
100	100	7
1000	1000	10
10⁶	10⁶	20
10⁹	10⁹	30

Для бинарного поиска массив должен быть отсортирован, в общем случае сортировка требует времени O(NlogN).

Если элемент ищется лишь один раз, а массив не отсортирован, то выгоднее использовать линейный поиск (O(N) выгоднее, чем O(NlogN) + O(logN));
Если элементы ищутся много раз, то выгоднее отсортировать массив и использовать бинарный поиск (O(NlogN) + много O(logN) выгоднее, чем много O(N));
Если элементы добавляются и удаляются, то вместо отсортированного массива следует использовать другую коллекцию — двоичное дерево поиска или хеш-таблицу;
При помощи хеш-таблицы можно решать исходную задачу эффективнее, чем двоичным поиском, — за константное время (O(1)). Но идея двоичного поиска применима в существенно более широком наборе задач, как мы увидим далее.

Левый и правый бинарный поиск

Рассмотренная выше задача, в которой требуется найти любое вхождение заданного элемента в массив, встречается сравнительно редко и представляет мало интереса. Гораздо важнее другой вид задач: дан отсортированный массив a[] и требуется найти в нём индекс первого или последнего вхождения числа x (или индекс последнего элемента, меньшего x, или индекс первого элемента, большего x).

При решении данной задачи мы уже не можем сразу вернуть индекс, как только нашли элемент, равный x, и функцию поиска придётся усложнить.

Оказывается, что написание бинарного поиска первого или последнего вхождения — достаточно трудная задача. Программист вынужден держать в голове множество тонких моментов. Вот некоторые из них:

Является ли диапазон от l до r отрезком или полуинтервалом, как он отсортирован, содержит ли он искомый элемент;
Как следует проверять центральный элемент и как смещать границы: l = m или l = m + 1, r = m или r = m - 1;
Будет ли поиск правильно работать на массивах из 0, 1, 2 элементов;
Какой из индексов в итоге указывает на ответ, как проверить, что ответ отсутствует, и др.

Правила написания бинарного поиска без головной боли

Диапазон от l до r — всегда отрезок (включительно, [l; r]), изначально l = 0, r = size - 1. Искомый элемент изначально может как быть в отрезке, так и не быть, это не важно;
Поиск всегда осуществляется до двух элементов (while (l + 1 < r));
После проверки среднего элемента границы всегда смещаются только на середину (l = m или r = m, никаких плюс-минус единиц);
Смещение границ должно происходить так, чтобы не потерять искомый элемент (чтобы он не выпал из отрезка [l; r], если он там был).

Пример: массив отсортирован по неубыванию, ищем первый элемент, равный x. Простые, очевидные случаи: если a[m] < x, то l = m; если a[m] > x, то r = m. Более важный и трудный случай: a[m] == x. Если мы сдвинем левую границу, то можем потерять первый x, а если сдвинем правую — не потеряем. Поэтому нужно двигать правую: r = m.

Подобным же образом нужно рассуждать во всех аналогичных задачах. Запоминать условия не нужно.

Когда цикл завершится, останутся два соседних элемента — a[l] и a[r]. Их нужно проверить по отдельности. При этом, если мы ищем первое вхождение чего-либо, то сначала проверяем a[l], затем a[r]; если ищем последнее вхождение — сначала a[r], затем a[l].

Следуя этим правилам, вы сможете практически единообразно писать различные виды левых и правых двоичных поисков. Сравните показанные ниже примеры: в них меняются только условие проверки среднего элемента (выделено красным) и порядок проверки последних двух элементов (выделено оранжевым).

// сорт. по неубыванию
// последний элемент < x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] < x)
        l = m;
    else
        r = m;
}
if (a[r] < x)
    return r;
if (a[l] < x)
    return l;
return -1;

// сорт. по неубыванию
// последний элемент <= x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] <= x)
        l = m;
    else
        r = m;
}
if (a[r] <= x)
    return r;
if (a[l] <= x)
    return l;
return -1;

// сорт. по неубыванию
// последний элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] <= x)
        l = m;
    else
        r = m;
}
if (a[r] == x)
    return r;
if (a[l] == x)
    return l;
return -1;

// сорт. по неубыванию
// первый элемент > x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] <= x)
        l = m;
    else
        r = m;
}
if (a[l] > x)
    return l;
if (a[r] > x)
    return r;
return -1;

// сорт. по неубыванию
// первый элемент >= x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] < x)
        l = m;
    else
        r = m;
}
if (a[l] >= x)
    return l;
if (a[r] >= x)
    return r;
return -1;

// сорт. по неубыванию
// первый элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] < x)
        l = m;
    else
        r = m;
}
if (a[l] == x)
    return l;
if (a[r] == x)
    return r;
return -1;

// сорт. по невозрастанию
// последний элемент > x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] > x)
        l = m;
    else
        r = m;
}
if (a[r] > x)
    return r;
if (a[l] > x)
    return l;
return -1;

// сорт. по невозрастанию
// последний элемент >= x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] >= x)
        l = m;
    else
        r = m;
}
if (a[r] >= x)
    return r;
if (a[l] >= x)
    return l;
return -1;

// сорт. по невозрастанию
// последний элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] >= x)
        l = m;
    else
        r = m;
}
if (a[r] == x)
    return r;
if (a[l] == x)
    return l;
return -1;

// сорт. по невозрастанию
// первый элемент < x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] >= x)
        l = m;
    else
        r = m;
}
if (a[l] < x)
    return l;
if (a[r] < x)
    return r;
return -1;

// сорт. по невозрастанию
// первый элемент <= x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] > x)
        l = m;
    else
        r = m;
}
if (a[l] <= x)
    return l;
if (a[r] <= x)
    return r;
return -1;

// сорт. по невозрастанию
// первый элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] > x)
        l = m;
    else
        r = m;
}
if (a[l] == x)
    return l;
if (a[r] == x)
    return r;
return -1;

// f() возвращает 
// сначала true, потом false
// последний f() == true
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (f(a[m]))
        l = m;
    else
        r = m;
}
if (f(a[r]))
    return r;
if (f(a[l])
    return l;
return -1;

// f() возвращает 
// сначала false, потом true
// первый f() == true
int l = 0, r = size - 1;
while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (!f(a[m]))
        l = m;
    else
        r = m;
}
if (f(a[l])
    return l;
if (f(a[r]))
    return r;
return -1;

Ссылки

Теория:

Код:

CodeLibrary — Binary search

Задачи:

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

Содержание