Одномерные массивы. Алгоритмы поиска элемента массива

Содержание

1. Одномерные массивы. Алгоритмы поиска элемента массива
2. Линейный поиск.Алгоритм. Последовательно просматриваем массив и сравниваем значение
3. Улучшим: будем прерывать поиск, как только найдем элемент:while (i
4. Бинарный поиск Применяется для отсортированных массивов!!!!!!!.
5. Алгоритм Является ли Х средним элементом массива.
6. begin l := 1; r := n;
7. Задача. Дано Х и массив А(n), отсортированный
8. Скачать презентанцию

Линейный поиск.Алгоритм. Последовательно просматриваем массив и сравниваем значение очередного элемента с данным, если значение очередного элемента совпадет с Х, то запоминаем его номер в переменной k.For i := 1 to n

Главная
Информатика
Одномерные массивы. Алгоритмы поиска элемента массива

Слайды и текст этой презентации

Слайд 1Одномерные массивы
Алгоритмы поиска элемента массива

Слайд 2Линейный поиск.
Алгоритм.
Последовательно просматриваем массив
и сравниваем значение очередного элемента с

данным, если значение очередного элемента совпадет с Х, то запоминаем

его номер в переменной k.
For i := 1 to n do if a[i] = x then k := i;
Недостатки данной реализации алгоритма:
находим только последнее вхождение элемента
в любом случае производится n сравнений

Линейный поиск.Алгоритм. Последовательно просматриваем массив и сравниваем значение очередного элемента с данным, если значение очередного элемента совпадет с

Слайд 3
Улучшим: будем прерывать поиск, как только найдем элемент:
while (i

n ) and ( a[i] x) do inc(i);
В результате

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

Улучшим: будем прерывать поиск, как только найдем элемент:while (i

Слайд 4 Бинарный поиск
Применяется для отсортированных массивов!!!!!!!.

Слайд 5Алгоритм
Является ли Х средним элементом массива. Если да, то

поиск завершен, иначе переходим к пункту 2.
Возможно 2 случая:
Х меньше

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

Алгоритм Является ли Х средним элементом массива. Если да, то поиск завершен, иначе переходим к пункту 2.Возможно

Слайд 6begin
l := 1; r := n; {на первом шаге

рассматриваем весь массив}
f := false; {признак того, что Х

не найден}
while ( l <= r ) and not f do
begin
m := (l+r) div 2;
if a[m] =x then f := true {элемент найден! Поиск прекращаем}
else if x < a[m] then r:=m-1 {отбрасываем правую часть}
else l := m + 1 {отбрасываем левую часть}
end;