Схема алгоритма линейного поиска

Государственное образовательное учреждение среднего профессионального образования

ВОРКУТИНСКИЙ ГОРНО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ

РАССМОТРЕНО УТВЕРЖДАЮ:

На заседании цикловой комиссии Зам. директора по УВР

«___»_____________2008 г. ______________З.Г. Штокалюк

Председатель цикловой комиссии «___»___________2008 г.

____________ О.В. Гармаш

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к лабораторной работе № 15

Тема:

«Методы поиска данных»

Дисциплина: «Программирование на языке высокого уровня»

для студентов специальности 230101

Разработал преподаватель Баев А.В.

2008 г.

Лабораторная работа №15

Методы поиска данных

Цель работы:

1. Изучить алгоритмы поиска.

2. Приобрести навыки программирования задач поиска данных различных типов.

Краткие сведения из теории

Наряду с задачей сортировки актуальной при работе с данными является поиск данных по заданному признаку. Если данные не упорядочены, то для поиска приходится просматривать весь объем информации. В том случае, если данные упорядочены, для поиска используют один из двух известных алгоритмов поиска: линейный или двоичный поиск. Рассмотрим эти алгоритмы и реализующие их программы.

Пусть задан массив Х, содержащий n целых чисел, расположенных в порядке возрастания значений. Требуется найти заданное число isk.

Линейный поиск

Линейный поиск заключается в последовательном сравнении элементов упорядоченного массива Х с искомым значением isk. Поиск в этом случае заканчивается в двух случаях:

1. Очередной элемент массива Х равен искомому значению isk, в этом случае элемент найден.

2. Очередной элемент массива Х больше искомого значения, а так как все последующие элементы также больше isk, то искомого элемента не может быть в Х.

Схема алгоритма линейного поиска

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