Описание тега binary-search

Описание тега Вопросы с тегом

Двоичный поиск - это эффективный алгоритм поиска элемента в отсортированном массиве. Основная идея состоит в том, чтобы на каждом этапе сокращать пространство поиска вдвое. Сложность алгоритма - O(log(n)).

Двоичный поиск алгоритм (или "полуинтервал поиска") находит позицию заданного значения ("ключ" вход) в отсортированном массиве. На каждом шаге алгоритм сравнивает входное значение ключа со значением ключа среднего элемента массива. Если ключи совпадают, то соответствующий элемент был найден, поэтому возвращается его индекс или позиция. В противном случае, если искомый ключ меньше, чем ключ среднего элемента, то алгоритм повторяет свое действие на субмассиве слева от среднего элемента или, если входной ключ больше, на субмассиве справа. Если оставшийся массив для поиска уменьшается до нуля, то ключ не может быть найден в массиве и возвращается специальная индикация "Не найден".

Бинарный поиск уменьшает вдвое количество проверяемых элементов на каждой итерации, поэтому поиск элемента (или определение его отсутствия) занимает логарифмическое время. Бинарный поиск - это дихотомический алгоритм поиска " разделяй и властвуй".

Псевдокод и примеры на нескольких языках см. На этой странице Code Codex.