Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Весь массив просмотрен и совпадения не обнаружено.






Это дает нам линейный алгоритм:

i: = 1;

WHILE (i < = N) and (a[i] < > x) DO i: = i + 1; (5.1)

Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:

(1 ≤ i ≤ N) & (A k: 1 ≤ k < i: ak ≠ x) (5.2)

Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие:

((i = N + 1) OR (аi = х)) & (A k: 1 ≤ k < i: ak ≠ х)

Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N + 1 свидетельствует, что совпадения не существует.

Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N + 1; фактически же, если совпадения не было, это произойдет после N + 1 шагов.

Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск? Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением х. Назовем такой вспомогательный элемент «барьером», ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так: a: ARR AY [1 ..N + 1] OF INTEGER и алгоритм линейного поиска с барьером выглядит следующим образом:

i: = 1; a[N + 1]: = x;

WHILE (a[i] < > x) DO i: = i + 1; (5.3)

Результирующее условие, выведенное из того же инварианта, что и прежде:

i = х)) & (A k: 1 ≤ k < i: ak ≠ х)

Ясно, что равенство i = N + 1 свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

 

· ТЕМА 2. ПОИСК ДЕЛЕНИЕМ ПОПОЛАМ (ДВОИЧНЫЙ ПОИСК)

Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно, более эффективным, если данные будут упорядочены. Вообразите себе телефонный справочник, в котором фамилии не будут расположены по порядку. Это нечто совершенно бесполезное! Поэтому мы приводим алгоритм, основанный на знании того, что массив а упорядочен, т.е. удовлетворяет условию

A k: 1 ≤ k ≤ N: ak - 1 ≤ ak (5.4)

Основная идея - выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска х. Если он равен х, то поиск заканчивается, если он меньше х, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше х, то исключаются индексы больше и равные т. Это соображение приводит нас к следующему алгоритму (он называется «поиском делением пополам»). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.

L: = 1; R: = N; found: = FALSE; (5.5)

WHILE (L< =R) and NOT found DO

BEGIN

m: = (L + R) DIV 2; { выбираем любой элемент между элементами с номерами L и R }

IF a[m]=x THEN found: = TRUE ELSE

IF a[m] < x THEN L: = m + 1 ELSE R: =m – 1;

END;

IF found THEN writeln(‘ искомый элемент ‘, a [m]);

Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:

(L ≤ R) & (A k: 1 ≤ k < L: ak < х) & (A k: R < k ≤ N: ak > х) (5.6)

из чего выводится результат

found OR ((L > R) & (A k: 1 ≤ k < L: ak < х) & (A k: R < k ≤ N: ak > х))

откуда следует

(am = x) OR (A k: 1 ≤ k ≤ N: ak ≠ х).

Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log2 (N), округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N / 2.

Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log2 (N). Быстрый алгоритм основан на следующем инварианте:

(A k: 1 ≤ k < L: ak < х) & (A k: R < k ≤ N: ak ≥ х) (5.7)

причем поиск продолжается до тех пор, пока обе секции не «накроют» массив целиком.

L: = 1; R: = N + 1;






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.