Двоичный поиск
Давайте посмотрим на другой пример рекурсии, который имеет широкий спектр применений.
Когда мы обсуждали массивы, мы кратко рассмотрели задачи сортировки и поиска.
Сортировка и поиск являются двумя из наиболее часто используемых операций в компьютерных приложениях, и они часто используются вместе, потому что, если данные отсортированы, операция поиска может быть выполнена гораздо более эффективно.
Если вы до сих пор помните те времена, когда вы смотрели на значение слова из бумажного словаря или некоторые имена из телефонной книги, вместо того чтобы всегда искать информацию с начала словаря или каталога, вы начнете где-то посередине, потому что вы знаете, что слова или имена уже перечислены в алфавитном порядке.
Идея бинарного поиска следует подобной идеи.
Обратите внимание, что бинарный поиск будет работать только для отсортированных массивов.
Вместо того, чтобы начать поиск с начала массива, идея бинарного поиска в том, чтобы начать с середины.
При этом сначала сравнивается искомый элемент со средним элементом массива.
Если соответствие нашли, тогда поиск будет успешным.
В противном случае, применяется бинарный поиск к той половине массива, где искомый элемент, вероятно, может быть найден.
Обратите внимание, что поскольку массив отсортирован, поиск элемента может быть сделан только в одной из двух половинок матрицы, если он есть вообще.
Рассмотрим пример.
Вы можете видеть, что здесь есть массив из неизвестных элементов, и мы пытаемся найти значение 14 в этом массиве.
Разделим массив на две части.
В начале, весь массив неизвестен, но отсортирован.
Теперь, мы будем искать значение 14 в этом массиве.
Разделим массив на две части, и изучим среднюю величину, является ли оно равным значению нашего поиска.
Индекс среднего значения вычисляется по формуле (start_index + end_index) / 2. В этом случае это индекс 4.
Значение 10 не наша искомая величина, так что мы продолжаем поиск.
Так как массив отсортирован, часть перед текущим значением должна быть меньше, чем 10.
И теперь мы знаем, что все значения в этой части также меньше, чем искомое значение 14.
Таким образом, мы можем оставить левую часть и сделать проверку только в правой части.
Теперь, продолжим нашу проверку в этой оставшейся части.
Разделим эту часть на две части и изучим среднюю величину, то есть величину с индексом 7.
Мы можем сделать вывод, что искомое значение теперь не в правой части.
Повторите этот процесс на оставшейся части путем определения, является ли среднее значение искомым значением.
Мы нашли наше искомое значение 14, которое здесь имеет индекс 6.
Двоичный поиск может быть осуществлен путем прямой передачи этой идеи в Java коде с помощью рекурсии.
Здесь показана реализация двоичного поиска данных, хранимых в целочисленном массиве.
Переменные lower и upper являются двумя ограничивающими индексами для части массива, где программа в настоящее время ведет поиск.
В начале, будет lower = 0 и upper будет размером массива, если вы хотите искать для всего массива.
Переменная value представляет данные, которые вы ищете.
Программа начинается с определения среднего индекса в массиве, который является просто (lower + upper) / 2.
Затем программа проверяет, равен ли средний элемент значению, которое вы ищете, и если это правда, это значение находится и индекс возвращается.
Если переменная lower больше или равна переменной upper, это означает, что программа выполнила поиск в массиве полностью и элемент нельзя найти, поэтому возвращается значение -1.
Далее идет рекурсивная часть, где, если искомое значение меньше среднего элемента, то так как массив отсортирован, значение может быть только в начале половины массива, если оно вообще там есть.
И вызов бинарного поиска делается путем изменения верхнего индекса на middle-1, таким образом, что только первая половина массива ищется на следующем этапе.
Если код else выполняется, то есть, когда искомое значение больше среднего элемента, искомый элемент может быть только во второй половине массива, если он есть вообще, поэтому поиск выполняется только в части с индексом middle+1 до первоначального верхнего индекса.
Обратите внимание, что рекурсивный вызов binSearch производится в двух местах, но с разными ограничивающими индексами.
Поскольку диапазон индексов продолжит уменьшаться в рекурсивном вызове, для массива фиксированного размера, он в конечном итоге достигнет базового случая, как указано здесь.
Вы можете реализовать бинарный поиск, используя итеративный подход.
Перевод бинарного поиска в итерационный метод должен быть довольно простым.
Вместо того чтобы использовать рекурсивный вызов, вы можете использовать while цикл.
Было бы хорошим упражнением для вас попробовать реализовать бинарный поиск, используя итеративный подход.
Давайте посмотрим на демонстрацию программы бинарного поиска.
Здесь мы используем целый массив data для хранения контента для поиска, который будет проводиться.
Переменная nTimes используется для отслеживания количества раз, сколько было сделано рекурсивных вызовов, потому что я хочу сказать немного о эффективности алгоритма двоичного поиска.
Метод binSearch здесь такой же, как тот, который мы только что описали, кроме того, что nTimes увеличивается на 1 каждый раз, когда binSearch вызывается.
Мы также создали метод demo с одним параметром, который дает текущее значение для поиска.
Здесь мы создаем большой массив с 1000 элементами, потому что мы хотим получить представление о эффективности алгоритма двоичного поиска.
Каждый элемент массива данных просто инициализируется в то же значение, что и его индекс.
Затем вызывается метод binSearch с 0 в качестве нижней границы индекса, и size-1 в качестве верхней границы индекса таким образом, что поиск будет охватывать весь массив.
Обратите внимание, что верхняя граница size-1, потому что это максимальный индекс массива.
Перед завершением метода demo, выводится nTimes.
Давайте скомпилируем программу, создадим экземпляр и запустим метод demo.
Значение для поиска вводится в качестве параметра.
Давайте попробуем 499.
Программа успешно находит индекс 499, и был сделан только один вызов binSearch.
Это происходит потому, что 499 находится в середине массива, то есть, когда вы добавляете 0 к 999, а затем делите на 2, используя целое деление; средний индекс получает значение 499.
Давайте снова запустим программу с 1000 в качестве входного значения.
Известно, что 1000 нет в массиве, поскольку максимальное значение 999.
Так что правильный результат возвращается -1.
Что интересно, это то, что количество вызовов binSearch здесь всего 10 раз.
Подумайте, сколько вызовов вы должны сделать, если вы ищете в массиве от начала до конца последовательно.
Для массива с 1000 элементов, вы должны пройти через 1000 сравнений прежде, чем может быть подтверждено, что искомого значения там не было.
Но с бинарным поиском только 10 сравнений необходимы.
В общем, вы можете увидеть, что для любого числа n, логарифм n с базой 2 это максимальное количество операций, которые необходимы для поиска.
Например, двоичный логарифм 1000 равен 9.99, так что бинарный поиск считается очень эффективным алгоритмом для больших n.
Но помните, что бинарный поиск будет работать, только если данные отсортированы.
Давайте попробуем еще раз запустить программу, на этот раз мы хотим найти значение 0.
Значение находится по индексу 0.
Но заметьте, что будут необходимы 9 вызовов для получения результата. Это происходит потому, что поиск начинается с середины.
Вы можете сказать, что было бы лучше, если бы мы начинали поиск с начала.
Это верно в этом случае, но в среднем, бинарный поиск, является гораздо более эффективным алгоритмом.
Эффективность алгоритма является важной темой в области компьютерных наук, хотя это выходит за рамки данного курса.
