Линейный и двоичный поиски в упорядоченном массиве

Массив одна из самых популярных структур данных и в тоже время, самых старых. С их помощью можно решать многие задачи связанный с хранением, поиском, удалением и добавлением данных. В Java массив представляет собой ссылку на область память, где хранятся данные массива.

Упорядоченный массив, представляет собой массив, в котором его элементы расположены в упорядоченном виде (по возрастанию/убыванию). Такие массивы используются в тех случаях, если при работе с ним, количество операций поиска элемента массива много больше операций вставок и удаления. Далее вы поймете почему.

И так, для поиска определенного элемента в массиве используют алгоритмы линейного и двоичного поиска. Рассмотрим каждый из них подробно для случая упорядоченного массива.

Алгоритм линейного поиска в упорядоченном массиве.

По сути алгоритм линейного поиска работает одинаково для упорядоченного и неупорядоченного массивов. Его суть заключается в последовательном переборе массива, начиная с первого(нулевого) элемента до тех пор, пока не будет найден нужный элемент. Стоит отметить, что этот алгоритм является эффективным для небольших массивов. Однако на практике в реальных прикладных программах такие случи довольно редки.

Заметим, что в среднем алгоритм работает за линейное время O(N).

Алгоритм двоичного поиска в упорядоченном массиве.

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

Реализация алгоритма представляет собой известную игру “Угадай число”. Например, кто-то загадывает число от 0 до 100 (пусть будет 20), а вам нужно угадать число. Вы говорите 50, а в ответ слышите “меньше”, вы говорите “25”, ответ “меньше”, вы – “13” – “больше”,  и т.д. пока не угадаете. Очевидно, что при каждой итерации мы уменьшаем выборку в два раза и так каждый раз. Мы выбираем среднее число между двумя концами и спрашиваем, больше оно или меньше искомого и исходя из ответа меняем концы выборки и повторяем.

В данном примере мы ищем число 49 в массиве из 100 элементов от 1 до 100. Обратим внимание на количество шагов, которые нам понадобились. 6 шагов двоичного поиска, против 48 шагов линейного имеем разницу в 6 раз!!! Алгоритм двоичного поиска работает в среднем O(log N).

P.S. В стандартной библиотеки Java (java.util.Arrays)  есть метод двойного (бинарного) поиска:

Оставить комментарий:

Ваш email не будет опубликован.