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