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

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

Рассмотрим задачу: дан массив 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
106	106	20
109	109	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) // if (a[m] > x) l = m; // r = m; else // else r = m; // l = 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) // if (a[m] >= x) l = m; // r = m; else // else r = m; // l = 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) // if (a[m] >= x) l = m; // r = m; else // else r = m; // l = 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) // if (a[m] < x) l = m; // r = m; else // else r = m; // l = 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) // if (a[m] <= x) l = m; // r = m; else // else r = m; // l = 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) // if (a[m] <= x) l = m; // r = m; else // else r = m; // l = 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])) // if (f(a[m])) l = m; // r = m; else // else r = m; // l = m; } if (f(a[l]) return l; if (f(a[r])) return r; return -1;

При желании показанный алгоритм можно оптимизировать, сократив количество проверок в конце.

Ссылки

Теория:

• Codeforces EDU — Двоичный поиск
• neerc.ifmo.ru/wiki — Целочисленный двоичный поиск
• neerc.ifmo.ru/wiki — Вещественный двоичный поиск
• brestprog — Бинарный поиск
• algorithmica.org — Бинарный поиск
• Калинин П. — Бинарный поиск
• Brilliant.org — Binary Search

Код:

• CodeLibrary — Binary search

Задачи:

• informatics.mccme.ru — Курс «Поиск и сортировка» — часть 2
• Задачи: Бинарный поиск