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

1. Поиск элемента в упорядоченном массиве

2.

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

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

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

4. Идея метода:

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

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

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

6.

7.

Ввод c
Перед осуществлением поиска
элемента нужно:
1. Массив сформировать
2. Массив отсортировать
p=0; first=1; last=n; found=false
k=(first+last) / 2
+
-
m[k] == c
found = true
+
first = k+1
p = p+1
-
(found)
ИЛИ(first>last)
+
m[k] > c
last = k-1

8.

+
Вывод k,p
found
c не
найдено