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

Бинарный поиск — это метод решения задач, который основан на делении пополам.

Одним из примеров бинарного поиска служит поиск слова в словаре. Пусть у нас есть англо-русский словарь и требуется найти перевод какого-то слова. Откроем словарь где-то в середине и сравним слово, написанное на открытой странице, с искомым словом. Если это слово идёт лексикографически (в алфавитном порядке) раньше, чем искомое слово, то искомое слово надо искать во второй половине словаря, а иначе его надо искать в первой половине словаря. Таким образом, за один шаг мы сократили диапазон поиска с целого словаря до половины словаря. Аналогично поступим на втором шаге – откроем такую страницу словаря, которая делит половину словаря, в которой находится искомое слово, на две равные части, и сравним написанное там слово с искомым словом. После второго шага мы сократим диапазон поиска до четверти словаря. Далее будем поступать аналогичным образом, каждый раз сокращая искомый диапазон страниц в два раза, пока он не сократится до одной страницы, на которой находится искомое слово.

Так как каждый раз диапазон поиска сокращается в два раза, то искомая страница будет найдена за \(O(log(n))\) шагов. Стоит отметить, что если на каждом шаге середина будет найдена не совсем точно, то диапазон поиска может сокращаться менее чем в два раза за один шаг, но асимптотика от этого не изменится.

Чтобы написать бинарный поиск для решения задачи, будем опираться на подход, который использует понятие инварианта. Любая задача на бинпоиск сводится к тому, что некоторое условие выполнено для всех натуральных (или целых) индексов до какого-то значения, а после этого значения условие не выполнено для всех индексов. И задача состоит в том, чтобы найти либо последний индекс, для которого условие выполнено, либо первый индекс, для которого условие не выполнено. Сначала необходимо найти целые индексы \(l\) и \(r\) такие, что для индекса \(l\) условие выполнено, а для индекса \(r\) условие не выполнено – это правило для индексов \(l\) и \(r\) сохраняется на всех шагах алгоритма и называется инвариантом. Далее на каждом шаге алгоритма бинарного поиска мы будем брать число в середине отрезка \([l; r]\), которое можно вычислить по формуле \(m = \lfloor {\frac{l + r}{2}} \rfloor\). Если условие для индекса m выполнено, то мы можем левую границу бинарного поиска сдвинуть в \(m\), тем самым перейдя от отрезка \([l; r]\) к отрезку \([m; r]\). Если же условие для индекса \(m\) не выполнено, то мы можем правую границу бинарного поиска сдвинуть в \(m\), тем самым перейдя от отрезка \([l; r]\) к отрезку \([l; m]\). В любом случае наш отрезок сократится примерно в два раза, что нам и требуется. Алгоритм бинарного поиска будет выполняться до тех пор, пока границы поиска \(l\) и \(r\) не станут двумя соседними числами. А так как при выполнении нашего алгоритма мы сохраняли инвариант, то на последнем шаге индекс \(l\) будет последним индексом, для которого условие выполнено, а индекс \(r\) будет первым индексом, для которого условие не выполнено.

while (r - l > 1) {
    m = (l + r) / 2;
    if (f(m))
        l = m;
    else
        r = m;
}

lowerbound и upperbound

Рассмотрим неубывающую функцию \(f\). Мы хотим найти первое целое значение \(x\), что \(f(x) \ge k\) и последнее целое \(y\), что \(f(y) < k\). Тогда мы также можем использовать бинарный поиск. Инвариант \(f(r) \ge k\) и \(f(l) < k\) называется \(lowerbound\). Индекс R будет задавать нижнюю границу.

while (r - l > 1) {
    m = (l + r) / 2;
    if (f(m) < k)
        l = m;
    else
        r = m;
}

Инвариант \(f(r) > k\) и \(f(l) \le k\) называется \(upperbound\). Индекс R будет задавать верхнюю границу.

while (r - l > 1) {
    m = (l + r) / 2;
    if (f(m) > k)
        r = m;
    else
        l = m;
}

Если \(f\) это просто отсортированный массив, то в стандартной библиотеке плюсов уже есть и \(lowerbound\), и \(upperbound\).

\(std::lowerbound(begin, end, x)\) возвращает первый итератор, значение элемента которого \(\ge x\)

\(std::upperbound(begin, end, x)\) возвращает первый итератор, значение элемента которого \(> x\)

Вещественный бинарный поиск

Бинарный поиск можно писать не только по целым индексам и значениям, но и для вещественных чисел. Например, некоторая задача на бинарный поиск по ответу может иметь не целое, а вещественное число в качестве ответа. В таком случае практически ничего не меняется, только лишь границы бинпоиска теперь будут вещественными числами и условие остановки алгоритма теперь будет выглядеть иначе.

Если в целочисленном бинарном поиске мы делаем итерации до тех пор, пока \(R − L > 1\), то в вещественном бинарном поиске необходимо делать итерации, пока не будет достигнута необходимая точность. Например, можно делать итерации до тех, пока \(R − L > \varepsilon\), где \(\varepsilon\) – достаточно маленькое число. Например, если нужна точность в 6 знаков после запятой, то можно с запасом взять \(\varepsilon = 10^{-7}\).

Например, \(lowerbound\) для неубывающей функции \(f\).

while (r - l > EPS) {
    m = (l + r) / 2;
    if (f(m) < k)
        l = m;
    else
        r = m;
}

Тернарный поиск

Пусть дана функция \(f(x)\) и отрезок \([l; r]\) такие, что функия на этом отрезке сначала строго возрастает, а потом строго убывает. То есть существует \(m \in [l; r]\) : на \([l; m]\) \(f(x)\) возрастает и на \([m; r]\) \(f(x)\) функция убывает. Необходимо найти m.

Возьмём любые две точки \(m_1\) и \(m_2\) в этом отрезке: \(l < m_1 < m_2 < r\). Посчитаем значения функции \(f(m_1)\) и \(f(m_2)\). Дальше у нас получается три варианта:

  • Если окажется, что \(f(m_1) < f(m_2)\), то искомый максимум не может находиться в левой части, т.е. в части \([l;m_1]\). В этом легко убедиться: если в левой точке функция меньше, чем в правой, то либо эти две точки находятся в области “подъёма” функции, либо только левая точка находится там. В любом случае, это означает, что максимум дальше имеет смысл искать только в отрезке \([m_1;r]\).
  • Если, наоборот, \(f(m_1) > f(m_2)\), то ситуация аналогична предыдущей с точностью до симметрии. Теперь искомый максимум не может находиться в правой части, т.е. в части \([m_2;r]\), поэтому переходим к отрезку \([l;m_2]\).
  • Если \(f(m_1) = f(m_2)\), то либо обе эти точки находятся в области максимума, либо левая точка находится в области возрастания, а правая — в области убывания (здесь существенно используется то, что возрастание/убывание строгие). Таким образом, в дальнейшем поиск имеет смысл производить в отрезке \([m_1;m_2]\), но (в целях упрощения кода) этот случай можно отнести к любому из двух предыдущих.

Осталось заметить, что мы не накладывали никаких ограничений на выбор точек \(m_1\) и \(m_2\). От этого способа, понятно, будет зависеть скорость сходимости (но и возникающая погрешность). Наиболее распространённый способ – выбирать точки так, чтобы отрезок \([l;r]\) делился ими на 3 равные части: \(m_1 = l + \frac{r - l}{3}\) и \(m_2 = r - \frac{r - l}{3}\).

Впрочем, при другом выборе, когда \(m_1\) и \(m_2\) ближе друг к другу, скорость сходимости несколько увеличится.

while (r - l > EPS) {
    m1 = l + (r - l) / 3,
    m2 = r - (r - l) / 3;
    if(f(m1) < f(m2))
        l = m1;
    else
        r = m2;
}