Здавалка
Главная | Обратная связь

Швидкий пошук в упорядкованому масиві

Самостійна робота 12.

Завдання: Скласти опорний конспект за темою. Написати програму для розв’язання задачі

 

Задача поиска существенно упрощается, если элементы массива упорядочены. Стандартный метод поиска в упорядоченном массиве - это метод деления отрезка пополам, причем отрезком является отрезок индексов 1..n. В самом деле, пусть m (k < m < l) - некоторый индекс. Тогда если A[m] > b, далее элемент нужно искать на отрезке k..m-1, а если A[m] < b - на отрезке m+1..l.

Для того, чтобы сбалансировать количество вычислений в том и другом случае, индекс m нужно выбирать так, чтобы длины отрезков k..m, m..l были (приблизительно) равными. Описанную стратегию поиска называют бинарным поиском. Алгоритм бинарного поиска – один из алгоритмов, полученных в результате применения одного из общих методов разработки эффективных алгоритмов – метода «разделяй и властвуй».

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

 

Program BinarySearch;

Const n = 100;

Var A : Array[1..n] of Real;

b : Real; Buffer : Real;

k, l, m : Integer;

Begin

{ Блок чтения упорядоченного массива A и элемента b }

k := 1; l := n;

Repeat

m := (k + l) div 2; Buffer := A[m];

If Buffer > b

then l := Pred(m) else k := Succ(m)

until (Buffer = b) or (l < k);

If A[m] = b

then Writeln(‘Индекс = ‘, m)

else Writeln( ‘Элемент не найден’)

End.

 

 


Рис 3. Бинарный поиск в упорядоченном массиве.

 

b – элемент, место которого необходимо найти. Шаг бинарного поиска заключается в сравнении искомого элемента со средним элементом A[m] в диапазоне поиска [k..l]. Алгоритм заканчивает работу при A[m] = b. Если A[m] > b, поиск продолжается слева от m, а если A[m] < b – справа от m. При l < k поиск завершается, и элемент не найден.

 

Нетрудно получить оценку числа С(n) сравнений метода. Пусть М - количество повторений цикла. Тогда М £ [log2 (n)]Поскольку на каждом шаге осуществляется 2 сравнения, в худшем случае

C(n) = 2[log2 n] = O(log2 n)

При n = 1000000 алгоритм совершает максимум 40 сравнений, в то время как линейный просмотр требует всех 1000000 сравнений.

Задача:Написати програму для пошуку у впорядкованому масиві елементів, що менші заданого N .

Література:

1 Ковалюк Т.В. Основи програмування. – Видавнича група BHV, 2005.-384 с. ISBN 966-552-138-1

Гриф надано Міністерством освіти і науки України, лист № 14/18.2-1564 від 08.07.2004 р.

2 Рапаков Г.Г., Ржеуцкая С.Ю. Turbo Pascal для студентов и школьников. – Санкт-Петербург. BHV, 2005.

3 Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0 – Киев «Век+», 2000 г.

 

 





©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.