Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Весь массив просмотрен и совпадения не обнаружено.
Это дает нам линейный алгоритм: 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;
|