База знаний гимназии 1 им. Барсукова

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

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

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

===== Описание: =====


Давайте рассмотрим данный алгоритм на примере задачи: ваш друг загадывает число из заданного заранее интервала [left, right], а вам требуется написать программу, которая будет отгадывать его (то есть ваш друг будет отвечать: "меньше", "больше" или "равно" на каждое предположение вашей программы). Заметим, что если заданный интервал достаточно большой, то обычный перебор всех возможных чисел будет работать очень долго (например если число может быть до 10<sup>18</sup>).


===== Алгоритм: =====


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


<file cpp 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);
</file>



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


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

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


<file cpp 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");
</file>




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



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


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

<file cpp 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;
    }
</file>



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



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

Воспользуемся бинарным поиском, за 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

База знаний гимназии 1 им. Барсукова

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

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

Инструменты страницы