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

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

Проще всего понять, что такое двоичный поиск, можно на примере игры в угадывание чисел. Смысл игры в том, что один игрок задумывает число внутри некоторого диапазона, например между 1 и 1000, а второй — пытается угадать это число за минимально возможное количество попыток. При каждой попытке второму игроку сообщается, является ли названное им число большим, меньшим или равным задуманному.

Прием быстрого угадывания чисел в этой игре основан на двоичной системе счисления. Чтобы угадать число между 1 и 1000, при первой попытке следует назвать 512 (29 = 512). Если нам скажут, что это число слишком велико, то задуманное число больше нуля и меньше 512, поэтому далее мы называем 256 (28= 256) — следующую меньшую степень двойки. Если же сказано, что названное число меньше задуманного, то задумано число большее 512 и для следующей попытки нужно прибавить 256 к 512 и назвать 768, и при каждой следующей попытке прибавлять следующую меньшую степень двойки. Если названное число больше задуманного, мы вычитаем эту степень двойки и прибавляем следующую меньшую степень.

Предположим, что первый игрок задумал 700. Отгадывающему следует называть такую последовательность чисел: 512, 768, 640, 704, 672, 688, 696 и, наконец, 700. При этом ему будет сообщаться, что первое число меньше, второе больше, третье меньше и т. д. На основании этой информации он будет вычислять следующее значение и, в конце концов, задуманное число будет отгадано за восемь попыток.

Если мы посмотрим на последовательность ответов первого «больше/меньше» из приведенного примера, то заметим интересную закономерность. Эта последовательность выглядит так: «меньше», «больше», «меньше», «больше», «меньше», «меньше», «меньше» и «равно». Если на место каждого ответа «больше» подставить 0, а на место каждого ответа «меньше» — 1, то мы получим двоичное число. Учитывая, что для задания любого числа между 1 и 1000 требуется 10 разрядов, можно представить 700 как 1010111100. Мы угадали это число, двигаясь слева направо и используя ответы «больше/меньше» для определения двоичной цифры в текущей позиции.

С использованием данного метода задуманное число всегда может быть найдено не более чем за 10 попыток. В нашем примере потребовалось только восемь попыток,так как число делится на 4 — степень двойки. Обратите внимание, что любое нечетное число потребует 10 попыток, по одной на разряд. Максимальное число попыток можно вычислить как логарифм 1000 по основанию 2. Иначе это значение можно определить, учитывая, что 2 = 1024. Для угадывания числа между единицей и миллионом по данному методу требуется лишь 20 или менее попыток. Приведенный пример иллюстрирует алгоритм двоичного поиска, который применяется для нахождения элемента индекса.

Структура, в которой все записи заполнены, считается сбалансированной. При поиске по сбалансированному индексу с n элементами требуется выполнить сравнение лишь для log2 n элементов. Наш пример с угадыванием чисел был сбалансированным, так как в последовательности присутствуют все числа. Но даже для сильно несбалансированных структур среднее число попыток возрастает менее чем на 10 процентов. Алгоритм двоичного поиска отлично работает для большого числа элементов, но обычно не рекомендуется, если их число меньше 50.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Поиск

Из книги автора

Поиск Поскольку каналы, на которые вы подписаны, в некотором роде являются вашей базой знаний, в ней нужно уметь эффективно ориентироваться – упорядочивать новости по типам, выделять запомнившиеся сообщения, искать нужные записи. Для этого Reader предлагает сразу


Поиск

Из книги автора

Поиск С количеством фотографий, производимых современными обладателями цифровиков, работа по разбору и классификации фотографий превращается в нетривиальное занятие: легкость съемки и дешевизна карт памяти привела к тому, что мы практически не удаляем снимки, даже


Поиск

Из книги автора

Поиск В процессе работы в компьютере накапливается большое количество файлов, и зачастую сориентироваться в них самостоятельно и найти нужный оказывается затруднительно. В этом случае вам на помощь придет система поиска. В Windows Vista она была значительно


Поиск на научных сайтах с использованием платформы Flexum «Поиск по научным сайтам»

Из книги автора

Поиск на научных сайтах с использованием платформы Flexum «Поиск по научным сайтам» Тема научного поиска не прошла мимо разработчиков персональных поисковиков. Подробному рассказу о возможностях таких поисковых систем посвящена отдельная глава нашей книги (см. главу 6).


RSS-поиск

Из книги автора

RSS-поиск Пополнять список своего RSS-агрегатора можно различными способами. Первый и наиболее распространенный – простой поиск сайтов по интересующим темам, а затем подписка на их RSS-ленты, если, конечно таковые имеются. Способ несложный, однако на редкость медленный и


Поиск

Из книги автора

Поиск Если вы хотите удалить пункт Поиск (Найти) из меню кнопки Пуск, то откройте разделHKEY_CURRENT_USER SoftwareMicrosoftWindowsCurrentVersionPoliciesExplоrer и создайте параметр NoFind типа DWORD со значением, равным 1.После перезагрузки пункт Поиск исчезнет из меню кнопки Пуск, а также исчезнет команда


Поиск

Из книги автора

Поиск Классический видЧтобы использовать классический вид поиска файлов без анимированного персонажа, то присвойте строковому параметру Use Search Asst значение no в разделе HKCUSoftwareMicrosoftWindowsCurrentVersionExplorerCabinetStateОчистка истории раннее вводимых словЕсли вы часто пользуетесь


Поиск

Из книги автора

Поиск Строка поискаЧтобы скрыть строку поиска из IE7, в разделе HKCUSoftwarePoliciesMicrosoftInternet ExplorerInfoDeliveryRestrictionsсоздайте параметр типа DWORD ·NoSearchBox· со значением 1. Перезапустите IE7, чтобы изменения вступили в силу. Кнопка Поиск (IE6)Чтобы изменить адрес поисковика, который у вас


Поиск

Из книги автора

Поиск На всех страницах сайта обязательно должно быть поле для поиска товаров. Удивительно, но в некоторых интернет-магазинах отсутствует поддержка поиска по сайту. Убедитесь, что на вашем сайте есть поиск. Более того, сделайте функцию поиска максимально заметной. Чаще


Двоичный поиск (Binary search)

Из книги автора

Двоичный поиск (Binary search) Все алгоритмы в этом разделе - версии двоичного поиска. Они работают с итераторами не произвольного доступа, уменьшая число сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов произвольного


Яндекс. Поиск – быстрый поиск документов

Из книги автора

Яндекс. Поиск – быстрый поиск документов Документы, как известно, имеют премерзкое свойство накапливаться. И чем больше документов, тем труднее в их залежах найти нужный. Электронные документы здесь не слишком отличаются от бумажных. Проблема места для хранения, правда,


Поиск

Из книги автора

Поиск Поиск величины при вводе Каким способом можно производить поиск подходящих величин в момент ввода? Табличный курсор (визуально) должен перемещаться к наиболее подходящему значению при добавлении пользователем новых символов водимой величины.Первоначально код


Поиск

Из книги автора

Поиск Управление отображением команды Поиск, которая также по умолчанию входит в состав меню кнопки Пуск, осуществляется в системном реестре в разделе HKEY_CURRENT_USERSoftwareMicrosoftWindowsCurrentVersionPoliciesExplorer с помощью REG_DWORD-параметра NoFind. Чтобы удалить данную функцию, следует присвоить


Глава 12 Поиск с предпочтением: эвристический поиск

Из книги автора

Глава 12 Поиск с предпочтением: эвристический поиск Поиск в графах при решении задач, как правило, невозможен без решения проблемы комбинаторной сложности, возникающей из-за быстрого роста числа альтернатив. Эффективным средством борьбы с этим служит эвристический


Поиск

Из книги автора

Поиск Проблема поиска информации существовала всегда. Поиск информации на локальном компьютере напоминает работу поисковых систем Интернета. В данном случае можно также выделить два основных направления поиска: обычный и усложненный. Под обычным подразумевается поиск