Двоичный поиск

Алгоритм двоичного поиска в упорядоченном массиве сводиться к тому, что мы берем элемент отсортированного массива и сравниваем с ключом X. Возможны три варианта:

- выбранный элемент ранен X. Поиск завершен.

- выбранный элемент меньше X. Продолжаем поиск в правой половине массива.

- выбранный элемент больше X. Продолжаем поиск в левой половине массива.

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

Верхняя оценка трудоемкости алгоритма двоичного поиска такова. На каждой итерации поиска необходимо два сравнения для первой версии, одно для второй версии. Количество итераций не больше, чем . Таким образом, трудоемкость двоичного поиска в обоих случаях

<== предыдущая страница	\|	следующая страница ==>
Метод сортировки	\|	Особенности реализации алгоритмов

Дата добавления: 2015-07-26; просмотров: 166; Нарушение авторских прав

Мы поможем в написании ваших работ!

lektsiopedia.org - Лекциопедия - 2013 год. | Страница сгенерирована за: 0.003 сек.