Метод двоичного поиска
Результатом работы алгоритма является индекс 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 – Блок-схема алгоритма бинарного поиска Задание. Написать программу поиска элемента массива двумя методами: на основе линейного просмотра, двоичного поиска. Предусмотреть время выполнения каждого метода в программе. Защитить программу.
|
