Слайд 2Линейный поиск.
Алгоритм.
Последовательно просматриваем массив
и сравниваем значение очередного элемента с данным, если
![Линейный поиск. Алгоритм. Последовательно просматриваем массив и сравниваем значение очередного элемента с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/996796/slide-1.jpg)
значение очередного элемента совпадет с Х, то запоминаем его номер в переменной k.
For i := 1 to n do if a[i] = x then k := i;
Недостатки данной реализации алгоритма:
находим только последнее вхождение элемента
в любом случае производится n сравнений
Слайд 3
Улучшим: будем прерывать поиск, как только найдем элемент:
while (i <= n )
![Улучшим: будем прерывать поиск, как только найдем элемент: while (i x) do](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/996796/slide-2.jpg)
and ( a[i] <> x) do inc(i);
В результате или найдем нужный элемент, или просмотрим весь массив.
Недостаток данной реализации:
в заголовке цикла сложное условие, что замедляет поиск.
Слайд 4 Бинарный поиск
Применяется для отсортированных массивов!!!!!!!.
Задача. Дано Х и массив А(n),
![Бинарный поиск Применяется для отсортированных массивов!!!!!!!. Задача. Дано Х и массив А(n),](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/996796/slide-3.jpg)
отсортированный по неубыванию Найти i, такой что a[i] = x или сообщить что данного элемента в массиве нет.
Слайд 5Алгоритм
Является ли Х средним элементом массива. Если да, то поиск завершен,
![Алгоритм Является ли Х средним элементом массива. Если да, то поиск завершен,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/996796/slide-4.jpg)
иначе переходим к пункту 2.
Возможно 2 случая:
Х меньше среднего, тогда так как А упорядочен, то из рассмотрения можно исключить все элементы массива, расположенные правее среднего и применить метод к левой половине массива.
Х больше среднего. Значит, исключаем из рассмотрения левую половину массива и применяем метод к правой части.