Алгоритмы последовательного поиска
«Начни с начала и продвигайся, пока не найдёшь нужный ключ; тогда остановись». Такая последовательная процедура является очевидным способом поиска; удобно начать наши рассмотрения с неё, так как на ней основаны многие более сложные алгоритмы. Несмотря на свою простоту, последовательный поиск содержит ряд очень интересных идей.
Все элементы списка пересматриваются последовательно в порядке их размещения, пока не найдётся элемент, равный ключу поиска. Если не известно, есть ли искомый элемент, то необходимо следить, чтобы поиск не вышел за границы списка. В таком случае техничным способом повышения эффективности программирования является введение стопера.
Алгоритм S. (Последовательный поиск.) Имеется таблица записей R1,R2,...,Rn, снабженных соответственно ключами K1,K2,...,Kn. Алгоритм предназначен для поиска записи с данным ключом K. Предполагается, что N≥ 1.
S1. Установить i ≤1.
S2. Если K=Ki, алгоритм оканчивается удачно.
S3. Если K<>Ki, увеличить i на 1.
S4.Если i<=N, то вернутся к шагу S2. В противном случае алгоритм оканчивается неудачно.
Алгоритм Q. (Быстрый последовательный поиск.) В отличие от алгоритма здесь ещё предполагается, что в конце файла стоит фиктивная Rn+1 запись.
Q1.Установить i <=1, Kn+1<=K.
Q2.Если K=Ki, то перейти на Q4.
Q3.Увеличить i на 1 и вернутся к шагу Q2.
Q4. Если i<=N, алгоритм оканчивается удачно; в противном случае - неудачно(i=N+1).
Алгоритм T. (Последовательный поиск в упорядоченной таблице.)
Имеется таблица записей R1,R2,...,Rn, причём ключи удовлетворяют неравенствам K1<K2<...<Kn. Алгоритм предназначен для поиска записи с данным ключом K. В целях удобства и увеличения скорости работы предполагается, что в конце таблицы расположена фиктивная запись Rn+1, ключ которой Kn+1= >K.
T1. Установить i <=1.
T2. Если K<=Ki, то перейти на T4.
T3. Увеличить i на 1 и вернутся к шагу T2.
T4. Если K=Ki, то алгоритм оканчивается удачно, в противном случае - неудачно, нужной записи в таблице нет.
Поиск в упорядоченной таблице
В нашем распоряжении есть много методов сортировки, поэтому для нас не составит труда упорядочить файл, чтобы потом быстрее произвести поиск. В этом пункте мы изучим методы поиска в таблице со случайным доступом и упорядоченными ключами K1<K2<...<Kn.
После сравнения K и Ki мы имеем:
n K < Ki [Ri,Ri+1,..., Rn исключаются из рассмотрения],
n K = Ki [ поиск закончен],
n K > Ki [R1,R2,...,Ri исключаются из рассмотрения].
Умело действуя в каждом из этих случаев, можно сэкономить много времени по сравнению с последовательным поиском, если только не слишком близко к концам таблицы. Таким образом, упорядочение ведет к эффективным алгоритмам.
Бинарный поиск
Пожалуй, первым приходит в голову следующий очевидный метод: сначала сравнить K со средним ключом в таблице. Результат сравнения позволит определить, в какой половине файла продолжить поиск, применяя к нему ту же процедуру, и т.д. После не более чем примерно log2 N сравнений либо ключ будет найден, либо будет установлено его отсутствие. Такая процедура иногда называется «логарифмическим поиском» или «методом деления пополам», но наиболее употребительный термин - бинарный поиск.
Недостатком бинарного поиска является необходимость последовательного сохранения списка, что осложняет выполнение операции добавления и удаления элемента.
Основная идея бинарного поиска довольно проста, детали же нетривиальны, и для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей. Одна из наиболее популярных реализаций метода использует два указателя - l и u, соответствующие верхней и нижней границам поиска, и состоит в следующем.
Алгоритм B. ( Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1,R2,...,Rn, ключи которых расположены в возрастающем порядке: K1<K2<...<Kn.
B1. [Начальная установка]. Установить l <=1, u<=1.
B2.[Нахождение середины]. (В этот момент мы знаем, что если K есть в таблице, то выполняются неравенства Kl £ K £ Ku.) Если u<l, то алгоритм заканчивается неудачно; в противном случае установить i £ (l-u)/2: теперь i указывает примерно в середину рассматриваемой таблицы.
B3.[Сравнение]. Если K<Ki, то перейти на B4; если K>Ki, то перейти на B5; если K=Ki, алгоритм заканчивается удачно.
B4. [Корректировка u]. Установить u<=i-1и вернуться к шагу B2.
B5.[Корректировка l]. Установить l<=i+1и вернуться к шагу B2.
Одна важная модификация. Соблазнительно вместо трёх указателей l, u, i использовать лишь два: текущее положение i и величину его изменения E; после каждого сравнения, не давшего равенство, мы могли бы установить i<=i+(-)E и E<=E/2(приблизительно). Этот путь реализуем, но он требует особой аккуратности в деталях, как в приведённом ниже алгоритме; более простые подходы обречены на неудачу!
Алгоритм U. ( Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1,R2,...,Rn, ключи которых расположены в возрастающем порядке: K1<K2<...<Kn.
U1. [Начальная установка]. Установить i <=N/2, m<=N/2.
U2.[Сравнение]. Если K<Ki, то перейти на U3; если K>Ki, то перейти на U4; если K = Ki, алгоритм заканчивается удачно.
U3. [Уменьшение i]. (Мы определили положение интервала, где нужно продолжать поиск. Он содержит m или m-1 записей; i указывает на первый элемент справа от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i<= i-(m/2); m<=m/2 и вернуться на U2.
U4. [Уменьшение i ]. ( Ситуация та же, что и в шагеU3, только i указывает на первый элемент слева от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i<= i+(m/2); m<=m/2 и вернуться на U2.
Фибоначчиев поиск
Алгоритм предназначен для поиска аргумента K в таблице значений R1,R2,...,Rn, расположеных в порядке возрастания ключей: K1<K2<...<Kn.
Для удобства описания предполагается, что N+1 есть число Фибоначчи Fk+1. Подходящей начальной установкой данный метод можно сделать пригодным для любого N
1. [Начальная установка]. Установить i <=Fk, p<=Fk-1, q <= Fk-2. (В этом алгоритме p и q обозначают последовательные числа Фибоначчи.)
2. [Сравнение]. Если K<Ki, то перейти на F3; если K>Ki, то перейти на F4; если K=Ki, алгоритм заканчивается удачно.
3. [Уменьшение i ]. Если q=0, то алгоритм заканчивается неудачно. Если q<>0,то установить i<= i-q, заменить (p,q) на (q,p-q) и вернуться на F2.
4.[Уменьшение i ]. Если p=1, то алгоритм заканчивается неудачно. Если p<>1,то установить i<= i+q, p<=p-q, q<=q-p и вернуться на F2.
Задача выбора
Формулирование задачи. В заданном линейном списке целых чисел B={K1,K2,...,Kn} (могут быть и одинаковые) необходимо найти элемент, который был бы расположен на i-ой позиции, если бы список B упорядочить по убыванию элементов. Это задача выбора i-ого наибольшего значения. В частности, для i=1 задача эквивалентна поиску в B элемента с наибольшим значением, для i=2 - поиск элемента со вторым наибольшим значением и т.д. Особый интерес вызывает задача выбора i-ого элемента, i= an, 0 <a< 1 для некоторых значений a, например, выбор медианы при a=1/2.
Алгоритм поиска наибольшего значения легко меняется на алгоритм поиска наименьшего значения.
Все варианты задачи выбора развязываются легко, если список B полностью отсортированный; тогда задача сводится до взятия в нём необходимого элемента.
Для развязывания задачи выбора i-ого наибольшего элемента в списке B={K1,K2,...,Kn} модифицирован алгоритм быстрой сортировки. Список делится элементом K1 на подсписки B1и B2, такие, что когда K принадлежит B1, то K>=K1, а когда K принадлежит B2, то K<K1. Список B реорганизуется в список B1,<K1>,B2, в котором K1 находится ан j-ом месте. Если j=i, то необходимый элемент найден; если j>i, то i-ое наибольшее значение ищется с подсписке B1; если j<i, то (i-j)-ое наибольшее значение ищется с подсписке B2.
Алгоритм выбора. Алгоритм на базе быстрой сортировки довольно эффективный для его выполнения необходимо количество действий порядка О(n). По некоторым причинам он может стать неэффективным, вымогая для своей реализации количества действий порядка O(n*n). Неэффективность объясняется тем, что K1 делит список B на неравные подсписки B1 и B2. Для улучшения алгоритма необходимо уметь находить в списке B элемент M, который разделяет список почти поровну.
ЗАКЛЮЧЕНИЕ
В заключение необходимо отметить, что данное пособие не может предоставить исчерпывающих сведений по методам, используемых в программировании. Кроме того, в нем представлены лишь основные методы. Более полную информацию можно получить в справочной литературе (см. ниже).
Перечень ссылок
1. Бахвалов Н.С. Численные методы. - М.: Наука, 1975.
2. Волков Е.А. Численные методы. - М.: Наука, 1982.
3. Горинштейн А.М. Практика решения инженерных задач на ЭВМ.- М.: Радио и связь, 1984.
4. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М.: Наука, 1984.
5. Самарский А.А. Введение в численные методы. - М.: Наука, 1982.
6. Щуп Т. Решение инженерных задач на ЭВМ. - М.: Мир, 1982.
7. Мудров А.Е. Численные методы для ПЭВМ на языках бейсик, фортран и паскаль. - Томск, МП ” Раско”, 1991.-272 с., ил.
8. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. - М.: Мир, 1985.-406 с.
9. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. - М. :Мир, 1978. Т.3. - 844 с.
10. Дьяконов В.П. Справочник по алгоритмам и программам для персональных ЭВМ: Справочник. - М.: Наука, 1987. - 240 с.
11. Каханер Д., Моулер К., Нэш С. Численные методы и математическое обеспечение: Пер. с англ. - М. :Мир, 1998.-575 с., ил.