Бинарный (двоичный) поиск.

Алгоритм двоичного поиска используется для организации процедуры поиска в упорядоченных массивах. Он основывается на простой идее разделения массива пополам до тех пор, пока искомый элемент не будет найден. Для начала нужно выбрать индекс середины массива и получить соответствующий ему центральный элемент. Если искомый ключ меньше центрального элемента, то поиск следует продолжить в левом подмассиве, а если больше — в правом. Если центральный элемент окажется равным искомому ключу, то прерываем выполнение цикла и возвращаем его в качестве результата. Данный метод будет работать только с отсортированными массивами!

Реализация алгоритма на языке Java:

Переменная i хранит результат поиска. перед началом работы ее значение равно -1. Если ключевой элемент найден не будет, то метод вернет значение. равное -1. Здесь мы первым делом отыскиваем средний элемент. Если он и есть наш искомый ключ, то его индекс просто присваиваем его переменной i, выходим из цикла и возвращаем результат. Для вычисления среднего элемента в целях оптимизации мы используем беззнаковый сдвиг вправо. Такой же подход используется и в уже готовой реализации метода Arrays.binarySearch() из пакета java.util. Если искомый ключ не равен среднему элементу, то мы определяем, больше он его или меньше. Если искомый элемент меньше, то мы уменьшаем пространство вдвое, так как правой границей массива теперь является значение переменной high. Если больше, то делаем вывод, что искать элемент нужно во второй половине массива.

Реализация алгоритма на языке С:

В итоге мы получаем очень быстрый и эффективный алгоритм поиска, вычислительная сложность которого определяется как O(lgN).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *