Лабораторная работа № 18.
Поиск элемента в массиве

Время выполнения

6 часов

Цель работы

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

Задачи лабораторной работы

После выполнения работы студент должен уметь применять алгоритмы поиска элемента в массиве при обработке данных;

Перечень обеспечивающих средств

Для обеспечения выполнения работы необходимо иметь компьютер со следующим математическим обеспечением: операционная система семейства Windows и С++Builder v.6.0.

Общие теоретические сведения

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

Поиск элемента массива на основе линейного просмотра

Результатом работы алгоритма линейного поиска значения Val в массиве A являются индекс Pos и логическая переменная ResultOk, которая принимает значение TRUE, если такой элемент содержится в массиве А, и FALSE - в противном случае. Индекс Pos принимает значение, равное номеру искомого элемента, если такой найден, и значение, равное -1 – в противном случае. 
Алгоритм линейного поиска: 
Шаг 1. Полагается Pos=-1 и ResultOk=FALSE, и значение переменной цикла J:=0. 
Шаг 2. Если A[J]=Val, то переменным Pos и ResultOk присваиваются соответственно значения Pos=J, ResultOk=TRUE и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу J=J+1. 
Шаг 3. Если J<Las (где Last – число элементов массива А), то выполняется Шаг 2, в противном случае – работа алгоритма завершена. 
Конец алгоритма. 
Схема алгоритма на основе линейного просмотра представлена на рис. 1.
 
Рисунок 1. Блок-схема алгоритма линейного поиска 

Метод двоичного поиска

Результатом работы алгоритма является индекс Pos, показывающий на место в упорядоченном массиве А с номерами элементов от First до Last, где располагается искомое значение Val. Также в качестве результата формируется логическая переменная ResultOk, которая принимает значение TRUE, если искомый элемент содержится в массиве А, и FALSE – в противном случае. 
Перед поиском исходный массив должен быть отсортирован любым методом.
Алгоритм двоичного поиска: 
Шаг 1. Полагается ResultOk=false; First=0; Last=N-1 (N-размер массива).
Шаг 2. Пока справедливо условие First<Last, выполняется Шаг 3. 
Шаг 3. Вычисляется середина массива Middle=(Last+First)/2. Если Val=А[Middle], то полагается First=Middle; Last=First; ResultOk=true (т.е. элемент найден); Pos=Middle, в противном случае проверяется условие Val>А[Middle]. Если это условие справедливо, то полагается First=Middle+1, в противном случае полагается Last=Middle-1. После чего управление передается на Шаг 1. 
Шаг 4. Если ResultOk=true, то выводится сообщение об успешном поиске и выводится индекс элемента Pos. В противном случае выдается сообщение что элемент не найден.
Конец алгоритма. 
Схема алгоритма на основе двоичного поиска представлена на рис. 2.
 Рисунок 2. Блок-схема алгоритма бинарного поиска