Меню Главная Случайная статья Настройки Двоичный поиск Материал из https://ru.wikipedia.org Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании. Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке. Содержание 1 Поиск элемента в отсортированном массиве 2 Приложения 3 См. также 4 Примечания 5 Литература 6 Ссылки Поиск элемента в отсортированном массиве Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом. Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска. Несмотря на то, что код достаточно прост, в нём есть несколько ловушек. Код (first + last) / 2 ошибочен, если first и last по отдельности умещаются в свой тип, а first+last — нет[1]. Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения: Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям, если имеем дело с неотрицательными целыми числами и first<last. Если first и last — указатели или итераторы, такой код единственно правильный, поскольку не нарушает абстракцию (уже операция «указатель + указатель» некорректна). Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «указатель+число указатель», «указательуказатель число». Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2. В Java сработает такой код: (first + last) >>> 1 (знаковое двоичное сложение совпадает с беззнаковым, Java гарантирует такое поведение даже при переполнении, и вся эта формула оперирует знаковыми числами как беззнаковыми). Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее. В двоичном поиске часты ошибки на единицу, и каждая такая ошибка превращается в зацикливание, пропуск или выход за пределы массива. Поэтому важно протестировать такие случаи: пустой массив (n=0), один элемент (n=1), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).[2] Например, функция std::lower_bound из C++ находит первый из равных, а std::upper_bound — элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить. Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям[1]. Приложения Практические приложения метода двоичного поиска разнообразны: Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом). Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции). Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до ${\displaystyle \varepsilon }$ можно за время ${\displaystyle \log _{2}1/\varepsilon }$. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт ${\displaystyle 1+\log _{2}N}$ времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально. См. также Линейный поиск Метод бисекции Метод дихотомии Метод Ньютона Метод золотого сечения Троичный поиск Примечания 1 2 Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken Архивная копия от 2 декабря 2013 на Wayback Machine // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка Архивная копия от 24 ноября 2013 на Wayback Machine В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x. Литература Левитин А. В. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 180—183. — 576 с. — ISBN 978-5-8459-0987-9 Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998. Ссылки Материал на сайте algolist Пошаговый разбор алгоритма, коды программ Как же всё-таки правильно написать двоичный поиск?