Исследование методов линейного и бинарного поиска
4.1. Цель работы:
- изучить методы линейного, бинарного и идексно-последовательного поиска.
- овладеть навыками написания программ для методов линейного, бинарного и индексно-последовательного поиска на языке программирования С++.
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к исследованию методов линейного, бинарного и индексно-последовательного поиска;
- ответить на контрольные вопросы и получить оценку по знанию теории;
- получить задание на выполнение конкретного варианта лабораторной работы и выполнить его;
- написать и отладить программу решения задачи на языке С++;
- составить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
Поиск – это действие наиболее часто встречающееся в программировании. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных по мере их появления. Существует несколько основных "вариаций этой темы", и для них создано много различных алгоритмов. При дальнейшем рассмотрении мы исходим из такого принципиального допущения: группа данных, в которой необходимо отыскать заданный элемент, фиксирована. Будем считать, что множество из N элементов задано, скажем, в виде такого массива
a: ARRAY[ 0..N-1 ] OF item
Обычно тип item описывает запись с некоторым полем, выполняющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному "аргументу поиска" x. Полученный в результате индекс i, удовлетворяющий условию a[i].key=x, обеспечивает доступ к другим полям обнаруженного элемента. Так как нас интересует в первую очередь сам процесс поиска, а не обнаруженные данные, то мы будем считать, что тип item включает только ключ, т.е. он есть ключ (key).
Линейный поиск
Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
1. Элемент найден, т.е. a[i] = x.
2. Весь массив просмотрен и совпадения не обнаружено.
Это дает нам линейный алгоритм:
i:= 0;
WHILE (i < N) AND (a[i] <> x) DO
i:= i+1;
END;
Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:
(0 £ i < N) AND (Ak: 0 £ k < i: ak ¹ x)
Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие его окончания:
((i = N) OR (ai = x)) AND (Ak: 0 £ k < i: ak ¹ x)
Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.
Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.
Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск?
Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент "барьером", ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так:
a: ARRAY[0..N] OF INTEGER
и алгоритм линейного поиска с барьером выглядит следующим образом:
a[N]:= x;
i:= 0;
WHILE a[i] <> x DO
i:= i+1;
END;
Результирующее условие, выведенное из того же инварианта, что и прежде:
(ai=x) AND (Ak: 0 £ k < i: ak ¹ x)
Ясно, что равенство i = N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.
Поиск делением пополам (двоичный поиск).
Совершенно очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Вообразите себе телефонный справочник, в котором фамилии не будут расположены по порядку. Это нечто совершенно бесполезное! Поэтому мы приводим алгоритм, основанный на знании того, что массив а упорядочен, т.е. удовлетворяет условию
Ak: 1£ k < N: ak-1 ¹ ak
Основная идея - выбрать случайно некоторый элемент, предположим a[m], и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Это соображение приводит нас к следующему алгоритму (он называется "поиском делением пополам"). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.
L:= 0;
R:= N-1;
found:= FALSE;
WHILE (L < R) AND NOT found DO
m:= любое значение между L и R;
IF a[m] = x THEN found:= TRUE;
IF a[m] < x THEN L:= m+1
ELSE R:= m-1;
ENDIF;
ENDWHILE;
Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:
(L £ R) AND (Ak: 0 £ k < L: ak < x) AND (Ak: R < k < N: ak > x)
из чего выводится результат
found OR ((L > R) AND (Ak: 0 £ k < L: ak < x) AND (Ak: R < k < N: ak > x))
откуда следует
(am = x) OR (Ak: 0 £ k < N: ak ¹ x)
Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log N, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N/2.
Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания закончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log N. Быстрый алгоритм основан на следующем инварианте:
(Ak: 0 £ k < L: ak < x) AND (Ak: R £ k < N: ak ³ x)
причем поиск продолжается до тех пор, пока обе секции не "накроют" массив целиком.
L:= 0;
R:= N;
WHILE L < R DO
m:= (L+R) DIV 2;
IF a[m] < x THEN L:= m+1
ELSE R:= m;
END
END
Условие окончания - L < R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R-L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L < m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m+1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а[R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а[R] = x. В отличие от первого нашего решения приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.
Еще одним вариантом убыстрения поиска в случае упорядоченности данных является индексно-последовательный поиск. При таком поиске организуется две таблицы: таблица данных со своими ключами - упорядоченных по возрастанию, и таблица индексов, которая тоже состоит из ключей данных, но эти ключи взяты из основной таблицы через определенный интервал. Другими словами, при прохождении упорядоченной таблицы мы сравниваем с ключом элементы не последовательно, а через определенный интервал, то есть задаем некоторый шаг поиска. Когда на очередном шаге поиска предыдущий элемент меньше значения ключа, а следующий элемент больше значения ключа, то устанавливаются соответственно нижняя low (kind<key) и верхняя hi (kind>key) границы в основной таблице. Между этими границами по основной таблице будет соответственно произвен уже обычный последовательный поиск.
Таблицы индексно-последовательного поиска
В псевдокоде алгоритм индексно-последовательного поиска следующий:
i = 1
while (i <= m) and (kind(i) <= key) do
i=i+1
endwhile
if i = 1 then low = 1
else low = pind(i-1)
endif
if i = m+1 then hi = n
else hi = pind(i)-1
endif
for j = low to hi
if key = k(j) then
search = j
return
endif
next j
search = 0
return
Эффективность данного вида поиска величина.
Данный вид поиска, также как и бинарный, может давать значительный эффект при больших размерах таблиц поиска. Рекомендованный шаг для n элементов таблице – приблизительно.
В принципе, для достижения наибольшей эффективности поиска при решении конкретных задач пользователь может задавать какой угодно шаг.
Линейный поиск
a: ARRAY[0..N] OF INTEGER
i:= 0;
WHILE (i < N) AND (a[i] <> x) DO
i:= i+1;
END;
Линейный поиск с барьером
a[N]:= x;
i:= 0;
WHILE a[i] <> x DO
i:= i+1;
END;
Поиск делением пополам (двоичный поиск).
Вариант 1
L:= 0;
R:= N-1;
found:= FALSE;
WHILE (L < R) AND NOT found DO
m:= любое значение между L и R;
IF a[m] = x THEN found:= TRUE;
IF a[m] < x THEN L:= m+1
ELSE R:= m-1;
ENDIF;
ENDWHILE;
Вариант 2
L:= 0;
R:= N;
WHILE L < R DO
m:= (L+R) DIV 2;
IF a[m] < x THEN L:= m+1
ELSE R:= m;
END
END
Индексно-последовательный поиск
i = 1
while (i <= m) and (kind(i) <= key) do
i=i+1
endwhile
if i = 1 then low = 1
else low = pind(i-1)
endif
if i = m+1 then hi = n
else hi = pind(i)-1
endif
for j = low to hi
if key = k(j) then
search = j
return
endif
next j
search = 0
return
Рассмотрим алгоритмы на языке С++, реализующие различные виды поиска.
В примерах таблицы поиска содержат только целочисленный ключ, а поля данных отсутствуют. Таблицы поиска задаются в виде одномерных массивов целых чисел (ключей записей).
Функция поиска для элемента по совпадению в неупорядоченной таблице возвращает индекс элемента либо -1 в случае отсутствия искомого элемента и имеет следующий вид:
/* ФУНКЦИЯ ПОИСКА ЭЛЕМЕНТА ПО СОВПАДЕНИЮ */
int poisk1(int A[],int n,int key)
{ int j = 0;
while (A[j]!= key && j < n-1)
j++;
return (A[j] == key)? j: -1;
}
Как было сказано выше, для улучшения алгоритма поиска можно использовать заграждающий элемент или барьер. В этом случае последняя запись таблицы запоминается, а после завершения поиска восстанавливается в таблице. В последний элемент массива заносится ключ поиска, и образуется так называемый заграждающий элемент.
Теперь на каждом шаге поиска осуществляется только одно сравнение, а сам поиск продолжается до нахождения элемента с заданным ключом. Если искомого элемента в исходной таблице не было, поиск закончится на барьере. Таким образом, использование барьера в случае числовых ключей существенно сокращает число сравнений. Если ключом поиска является символьная строка, то использование заграждающего элемента вряд ли оправдано.
/* ПОИСК ЭЛЕМЕНТА ПО СОВПАДЕНИЮ С ЗАГРАЖДАЮЩИМ ЭЛЕМЕНТОМ */
int poisk2(int A[],int n,int k)
{ int i = 0;
A[n] = k;
while (A[i]!= k)
i++;
return (i == n)? -1: i;
}
Как было сказано выше, в случае, если последовательность упорядочена по возрастанию (убыванию), можно использовать более эффективные методы поиска. Приведем листинг примера программы, которая осуществляет бинарный поиск в упорядоченной по возрастанию последовательности чисел.
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ Вариант 1 */
int bisearch1(int A[],int n,int key)
{ int li,rj,k;
li=0; rj=n-1;
while (li <= rj)
{ k = (li+rj)/2;
if (key > A[k])
li = k+1;
else
if (key < A[k])
rj = k-1;
else return k;
printf(" li=%d, rj=%d, k=%d ",li,rj,k);/* отладочная печать*/
}
return -1;
}
/* ========================================== */
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА Вариант 2,
оба варианта равноценны */
int bisearch(int A[],int n,int key)
{ int li,rj,k;
li=0; rj=n-1; k = li;
while (li <= rj && A[k]!= key)
{ k = (li+rj)/2;
if (key > A[k])
li = k+1;
else
if (key < A[k])
rj = k-1;
}
return (A[k] == key)? k: -1;
}
Еще одним эффективным методом поиска в упорядоченной таблице данных является индексно-последовательный поиск. Рассмотрим листинг программы, реализующей данный вид поиска в упорядоченной таблице данных.
/*ИНДЕКСНО-ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК*/
#include <iostream.h>
#include <conio.h>
struct index
{
int kind; int pind;
};
int poisk(int *mas) /*Функция индексно-последовательного поиска*/
{
const int n = 10;
int step, m;
cout<<"\n Введите шаг поиска \n";
cin>>step;
m = n/step;
int key;
cout<<"Введите ключ поиска"<<endl;
cin>>key;
index* masindex = new index [m];
int i =0;
int j =step-1;
int search;
while ((i<m)&&(mas[j]<=key)&&(j<n))
{
/*masindex[i].idx=i;*/
masindex[i].kind=mas[j]; masindex[i].pind=j;
if (masindex[i].kind == key)
{
search = j; delete mas; return search;
}
j=j+step; i++;
}
int hi, low;
if (i==0)
low = 0;
else
low = masindex[i-1].pind;
if (i == m)
hi =n-1;
else
hi = j - 1;
cout<<"Значение LOW = "<<low<<endl;
cout<<"Значение HIGH = "<<hi<<endl;
for (int z = low;z<=hi; z++)
{
if(key == mas[z])
{
search =z;
delete mas;
return search;
}
}
search=-1;
delete mas;
return search;
}
void main()
{
clrscr();
const int n = 10;
int mas[n];
cout <<" ----Ввод элементов массива в возрастающем порядке-----"<<endl;
for(int j = 0; j<n;j++)
{cout <<" Введите элемент массива с идексом "<<j<<endl; cin>>mas[j];}
int result;
result = poisk(mas);
if (result == -1)
cout<<"\n Таких элементов нет!\n";
else
cout<<"Найденный элемент имеет индекс = "<<result<<endl;
getch();
}
Следует обратить внимание, что в данном листинге для обеспечения ввода шага поиска пользователем используется динамический массив.
Задания
1. Найти наименьший элемент в упорядоченном массиве А с помощью линейного, бинарного и индексно-последовательного поиска.
2. Найти элементы в упорядоченном массиве А, которые больше 30, с помощью линейного, бинарного и индексно-последовательного поиска.
3. Вывести на экран все числа массива А кратные 3 (3,6,9,...) с помощью линейного, бинарного и индексно-последовательного поиска.
4. Найти все элементы, модуль которых больше 20 и меньше 50 в упорядоченной таблице, с помощью с помощью линейного, бинарного и индексно-последовательного поиска.
5. Вывести на экран все числа упорядоченного массива А кратные 4 (4,8,...) с помощью помощью линейного, бинарного и индексно-последовательного поиска.
6. Вывести на экран сообщение, каких чисел больше относительно 50 в упорядоченной таблице с помощью линейного, бинарного и индексно-последовательного поиска.
7. Найти элемент в упорядоченном массиве А и найти число сравнений помощью линейного, бинарного и индексно-последовательного поиска.
8. Поиск элементов случайным образом помощью линейного, бинарного и индексно-последовательного поиска.
9. Дан список номеров машин (345, 368, 876, 945, 564, 387, 230), найти, на каком месте стоит машина с заданным номером, линейный, бинарный и индексно-последовательный поиск.
10. Поиск каждого кратного двум элемента в упорядоченном массиве помощью линейного, бинарного и индексно-последовательного поиска.
11. Найти элемент с заданным ключом и число сравнений для его нахождения в упорядоченном массиве А с помощью линейного, бинарного и индексно-последовательного поиска.
12. Найти элемент с ключом, равным сумме индексов упорядоченного массива А с помощью линейного, бинарного и индексно-последовательного поиска.