Целочисленный двоичный поиск

Пусть мы хотим найти $x$ в отсортированном массиве $a$ длины $n$.

Применим концепцию из задачи "угадай число от $1$ до $100$".

Более формально. Используем идею метода "разделяй и властвуй" — посмотрим на элемент в середине массива $a\left[\frac{n}{2}\right]$. Если $a\left[\frac{n}{2}\right]=x$, то мы нашли $x$. Если $a\left[\frac{n}{2}\right]<x$, то $x$ может находиться среди элементов правее — $a\left[\frac{n}{2}+1,\dots ,n-1\right]$, так как все элементы левее $\frac{n}{2}$-го меньше $x$ (массив отсортирован). Если $a\left[\frac{n}{2}\right]<x$, аналогичными рассуждением получаем, что ответ стоит искать в $a\left[0,1,\dots ,\frac{n}{2}-1\right]$.

После первого $a\left[\frac{n}{2}\right]?x$ вопроса мы или угадали или получили нужный нам отрезок для поиска. Представим, что этот отрезок новый массив $a^{\prime }$. Теперь в отсортированном массиве $a^{\prime }$ надо найти элемент $x$.

Получается алгоритм использует "разделяй и властвуй" (на задаче на отрезке переходит на более малый отрезок), на каждой итерации он сравнивает с центральным элементов на отрезке и в случае неудачи сокращает длину отрезка в два раза. Итерации алгоритма совершаются пока мы не найдём $x$ или длина отрезка станет равна $0$.

Поскольку на каждом шаге длина отрезка уменьшается вдвое, это произойдёт через $O({\log }_{2}n)$ шагов.

Примерная реализация алгоритма двоичного поиска:

Функция binarySearch ищет $x$ в массиве $a$ длины $n$, возвращает индекс, по которому лежит $x$, или $-1$, если $x$ в массиве нет.

int binarySearch(int* a, int n, int x) {
  int l = 0, r = n - 1;
  while (l <= r) {
    int mid = (l + r) / 2;  // индекс элемента в центре отрезка [l, r]
    if (a[mid] == x) {
      return mid;
    } else if (a[mid] < x) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return -1;
}

На самом деле проще писать бинпоиск лишь с одним условием внутри. Подробнее написано в следующей главе.

int binarySearch(int* a, int n, int x) {
  int l = 0, r = n - 1;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (a[mid] < x) {
      l = mid;
    } else {
      r = mid;
    }
  }
  return a[r] == x || a[l] == x;
}

Проверка на a[l] = x нужна лишь если a[0] = x, так как в таком случае после поиска l будет равна 0.

Количество вхождений $x$ в массив

Дан массив $a$ и $q$ вопросов. Каждый запрос задан числом $x$. Для каждого запроса определите количество вхождений $x$ в массив $a$.

Решение : Отсортируем массив $a$. Для каждого $x$ с помощью бинпоиска найдём количество вхождений.

Для количества вхождений $x$ в отсортированном массиве $a$, достаточно получить индексы самого левого и самого правого вхождений $x$ в массив. Тогда количество вхождений — это разность этих индексов плюс один.

Сделаем два различных бинпоиска, для поиска l и r. Первый вернёт минимальное $i$ такое, что $a[i]\ge x$ или $n$ если все элементы $a$ меньше $x$. Второй найдёт максимальное $i$ такое, что $a[i]>x$ или $n$, если все элементы $a$ не больше $x$. В данном случае ответ будет разница этих индексов. В случае, если $x$ нет в массиве то результат будет $0$, так как $l=r$. В обычном мире первая функция называется lower_bound, а вторая lower_bound. Подробнее почитать про них в языке c++ можно тут и тут, а тут про их различие.