Презентация на тему "Одномерные массивы. Алгоритмы поиска элемента массива"

Содержание

• 
  Слайд 1

  Одномерные массивы

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

• 
  Слайд 2

  Линейный поиск.

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

• 
  Слайд 3
  

  Улучшим: будем прерывать поиск, как только найдем элемент: while (i x) do inc(i); В результате или найдем нужный элемент, или просмотрим весь массив. Недостаток данной реализации: в заголовке цикла сложное условие, что замедляет поиск.

• 
  Слайд 4

  Бинарный поиск

  Применяется для отсортированных массивов!!!!!!!.

• 
  Слайд 5

  Алгоритм

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

• 
  Слайд 6
  

  begin l := 1; r := n; {на первом шаге рассматриваем весь массив} f := false; {признак того, что Х не найден} while ( l

• 
  Слайд 7
  

  Задача.Дано Х и массив А(n), отсортированный по неубыванию Найти i, такой что a[i] = x или сообщить что данного элемента в массиве нет.