Лекция 8.Бинарный поиск элемента в упорядоченном линейном массиве

Слайд 2

Поиск в неупорядоченном массиве заключается в последовательном переборе элементов массива и сравнении

Поиск в неупорядоченном массиве заключается в последовательном переборе элементов массива и сравнении
их значений с искомым до того момента, пока результат сравнения не даст значение истина
Наиболее эффективные методы поиска работают только на упорядоченных наборах данных, для чего их предварительно сортируют

Слайд 3

Бинарный поиск (поиск методом деления пополам)

Является одним из эффективных методов поиска в

Бинарный поиск (поиск методом деления пополам) Является одним из эффективных методов поиска в больших отсортированных массивах
больших отсортированных массивах

Слайд 4

Идея метода:

делим массив пополам (определяем номер среднего элемента)
сравнивая искомый элемент со значением

Идея метода: делим массив пополам (определяем номер среднего элемента) сравнивая искомый элемент
среднего элемента массива, мы в состоянии сделать вывод, в какой половине он находится, т.е. сузить область дальнейшего поиска
затем делим пополам ту часть массива, в которой элемент обнаружен
так до тех пор, пока рассматриваемая часть массива не получится состоящей из одного элемента

Слайд 5

Список величин:

m – линейный упорядоченный массив
n – число элементов массива
k – индекс

Список величин: m – линейный упорядоченный массив n – число элементов массива
элемента (в центре области просмотра)
first – номер первого элемента области просмотра
last – номер последнего элемента области просмотра
c – искомое число
found – логический результат (найдено число или нет)
p – число повторов

Слайд 7

p=0; first=1; last=n; found=false

k=(first+last) / 2

m[k] == c

found = true

m[k] > c

first

p=0; first=1; last=n; found=false k=(first+last) / 2 m[k] == c found =
= k+1

last = k-1

p = p+1

Ввод c

(found) ИЛИ(first>last)

+

-

+

-

+

-

Перед осуществлением поиска элемента нужно:
Массив сформировать
Массив отсортировать

Имя файла: Лекция-8.Бинарный-поиск-элемента-в-упорядоченном-линейном-массиве.pptx
Количество просмотров: 34
Количество скачиваний: 0