Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

infa_1 / 14. Последовательный и бинарный поиск

..doc
Скачиваний:
35
Добавлен:
05.06.2015
Размер:
45.06 Кб
Скачать

14. Последовательный и бинарный поиск.

Последовательный поиск – исходное множество не упорядочено, имеется произвольный набор ключей k1, k2,…kn. Метод заключается в то, что отыскиваемый ключ ki последовательно сравнивается со всеми элементами множества. При этом поиск заканчивается досрочно, если элемент найден.

Бинарный поиск – исходное множество должно быть упорядоченно по возрастанию () (каждый последующий больше предыдущего). Отыскиваемый ключ сравнивается с центральным элементом. Если он меньше центрального, то поиск продолжается в левом подмножестве, иначе в правом. Номер центрального элемента находится по формуле: (n- число элементов в мн-ве, [..]-целая часть)