Швидкий пошук в упорядкованому масиві
Самостійна робота 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 Все права принадлежат авторам размещенных материалов.
|