Двоичный поиск при рекурсии в программировании

При двоичном поиске центральный элемент отсортированной области поиска сравнивается с элементом, который требуется найти. Существует три возможности. Если центральный элемент меньше целевого, убирается первая половина области поиска. Если он больше, убирается вторая половина области поиска. В третьем случае, когда центральный элемент равен целевому, поиск прекращается. Процесс повторяется с оставшейся частью области поиска до наступления третьего случая. Этот алгоритм напоминает оптимальную стратегию детской игры, в которой один из игроков угадывает число из заданного диапазона, а другой в случае неправильного ответа говорит «меньше» или «больше».
Так как двоичный поиск может быть описан как набор двоичных поисков во все уменьшающейся области, он поддается рекурсивной реализации. В метод нужно передать массив, в котором будет осуществляться поиск, пределы поиска и целевой элемент. Определить пространство поиска можно вычитанием нижнего предела из верхнего. Полученное значение делится пополам и добавляется к нижнему пределу. Это и будет индекс центрального элемента. Этот элемент сравнивается с целевым. В случае их равенства возвращается индекс. При меньшем целевом элементе новый верхний предел превращается в центральный индекс минус единица; при большем целевом элементе в центральный индекс плюс единица превращается новый нижний предел. Процедура повторяется до совпадения с целевым элементом.
Перед написанием кода рассмотрим возможные проблемные ситуации. Для этого вспомним, какие условия наложены на имеющиеся у нас данные, и подумаем, каким образом они могут быть нарушены. Первое условие фигурирует в самой задаче. Это поиск в отсортированном массиве. Если верхний предел в какой-то момент оказывается меньше нижнего, значит, сортировка не проводилась и нужно выбросить исключение.
Второе условие поиска чуть менее очевидно: предполагается, что в массиве присутствует целевой элемент. Если рекурсия останавливается только после обнаружения этого элемента, его отсутствие сделает процесс бесконечным.
Этого можно избежать, выбросив исключение в случае, когда верхний и нижний пределы совпали, а рассматриваемый при этом элемент отличен от целевого. Ну и наконец, предполагается, что нижний предел меньше или равен верхнему. Для простоты в этом случае можно выбросить исключение; хотя в реальной программе вы, скорее всего, определили бы это как недопустимый вызов и воспользовались бы для проверки утверждением.
Анализ рекурсии показывает, что каждый рекурсивный вызов используется только для изменения пределов поиска. Но это можно делать и на каждой итерации цикла, не тратя ресурсов на рекурсию.

Доставка и оплата:
AZMANO - торговая площадка, работающая по принципу интернет-магазина, где пользователям предоставляется возможность выгодно продавать или покупать товары и услуги различной тематики, неразрывно связанных с жизнью каждого из нас. AZMANO - это место для совершения выгодных покупок и продаж, а также отличный способ начать и развить свой собственный бизнес. Здесь можно найти товары, предоставленные как частными лицами, так и профессиональными продавцами, интернет-магазинами. Все товары Торговой площадки чётко классифицируются по своим разделам, что делает процесс поиска предельно быстрым и удобным. Размещение на AZMANO товаров и услуг бесплатно. Нет ограничений на количество выставляемых товаров и услуг. В целях повышения безопасности осуществления сделок купли-продажи на AZMANO, каждый новый продавец получает право выставлять товары на продажу только после успешного прохождения процедуры верификации. Для любителей коллекционирования создан раздел, включивший в себя наиболее популярные на сегодняшний день темы этого хобби. Не были забыты и любители спорта, увлекающиеся собирательством всевозможных спортивных материалов и атрибутики: программ, книг, справочников, журналов, шарфов, маек, значков, вымпелов и др. В соответствии с пожеланиями и потребностями пользователей будет расширяться классификация разделов и улучшаться функционал Торговой площадки. Администрация Торговой площадки всегда открыта для предложений и замечаний пользователей. Связаться с нами можно через форму обратной связи. Надеемся, что здесь каждый найдет для себя всё, что ищет: от массовых товаров до коллекционных раритетов. Добро пожаловать и удачных Вам сделок!

:
Безналичный расчет для юридических лиц Оплата электронными деньгами Оплата банковскими картами