Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




29.09.2022


28.09.2022


28.09.2022


27.09.2022


27.09.2022


26.09.2022





Яндекс.Метрика

Двоичный поиск

25.01.2021

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.

Поиск элемента в отсортированном массиве

  • Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
  • Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
  • Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
  • Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.
  • Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.

    • Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет? Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
      • Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям (то и другое — неотрицательные целые числа).
        • Если first и last — указатели или итераторы, такой код единственно правильный. Преобразование в uintptr_t и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число».
      • Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2. В Java соответственно: (first + last) >>> 1.
      • Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее.
    • В двоичном поиске часты ошибки на единицу. Поэтому важно протестировать такие случаи: пустой массив (n=0), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли?
    • Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент). Код на Си в такой ситуации находит первый из равных, более простой код на Си++ — какой попало.

    Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям.

    Приложения

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

    • Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
    • Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
    • Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до ε {displaystyle varepsilon } можно за время log 2 ⁡ 1 / ε {displaystyle log _{2}1/varepsilon } . Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1 + log 2 ⁡ N {displaystyle 1+log _{2}N} времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.