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

Результатом работы алгоритма является индекс Pos, показывающий на место в упорядоченном массиве А с номерами элементов от First до Last, где располагается искомое значение Val. Также в качестве результата формируется логическая переменная ResultOk, которая принимает значение TRU E, если искомый элемент содержится в массиве А, и 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 – Блок-схема алгоритма бинарного поиска

Задание.

Написать программу поиска элемента массива двумя методами: на основе линейного просмотра, двоичного поиска.

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

Защитить программу.