Инструменты пользователя

Инструменты сайта


бинарный_поиск

Это старая версия документа.


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

Данный алгоритм является основным алгоритмом поиска.

Описание:

Давай те рассмотрим данный алгоритм на примере задачи: ваш друг загадывает число из заданного заранее интервала [left, right], а вам требуется написать программу, которая будет отгадывать его (то есть ваш друг будет отвечать: «меньше», «больше» или «равно» на каждое предположение вашей программы). Заметим, что если заданный интервал достаточно большой, то обычный перебор всех возможных чисел будет работать очень долго (например если число может быть до 1018).

Алгоритм:

Давай те каждый раз брать середину интервала mid и если загаданное число меньше, то переходить к интервалу [l,mid], а иначе к [mid + 1, r]. Действительно, если элемент меньше mid, то и меньше всех элементов, которые находятся правее (то есть элементов больших чем mid). Так будем переходить от одного интервала к другому, пока left не совпадет с right, потому что в этот момент мы с уверенностью сможем сказать, что угадали число.

test1.cpp
    while (left < right)
      {
       int mid = (left + right) / 2;
       printf("%d", mid);
       scanf("%c", ans);
       if (ans == '=')
          {
          right = mid;
          break;
          }
       if (ans == '<')
          right = mid;
          else
          left = mid + 1;
      }
    printf("Загаданное число = %d", right);

Бинарный поиск в упорядоченных массивах:

Действовать будем абсолютно аналогично, только теперь left, right и mid - это индексы заданного массива.

Пусть нам нужно найти номер элемента равного key или вывести -1, если его нет в массиве:

test2.cpp
    while (left < right){
    int mid = (left + right ) / 2;
    if (a[mid] <= k)
        left = mid + 1;
    else
        right = mid;
    }
    if (a[right] == k)
    printf("%d", right);
    else
    printf("-1");

Бинарный поиск для монотонных функции:

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

Приведем пример для решения задачи о нахождении корня из N (>= 1) с точностью до 6 знаков:

test3.cpp
    right = N;
    left = 1;
    eps = 1e-7;
    while (fabs(left - right) > eps) {
    double mid = (left + right) / 2;
    if (mid * mid <= x)
        left = mid;
    else
        right = mid;
    }

Бинарный поиск по ответу:

Пусть нам дана какая то задача, где нужно максимизировать (минимизировать) ответ, но операция получения ответа достаточно трудоемка и мы не можем просто перебрать все возможные варианты.

Воспользуемся бинарным поиском, за left примем минимально возможный ответ по условиям задачи, а за right - максимально возможный. Теперь будем пробовать получить ответ равный mid = (left + right) / 2, если нам это удается, то left = mid, иначе right = mid.

Задачи, в которых можно использовать данный алгоритм:

http://informatics.mccme.ru/moodle/mod/statements/view.php?id=192

http://informatics.mccme.ru/moodle/mod/statements/view.php?id=1966

http://informatics.mccme.ru/moodle/mod/statements/view.php?id=3516

/home/m/mvgoru/wiki.gumnasion.ru/public_html/data/attic/бинарный_поиск.1385457660.txt.gz · Последние изменения: 2013/11/26 13:21 — Пронин Роман