Поиск
Лабораторная работа №4 (4 часа). Исследование методов линейного и бинарного поиска
Цель работы:
- изучить методы линейного, бинарного и идексно-последовательного поиска.
- овладеть навыками написания программ для методов линейного, бинарного и индексно-последовательного поиска на языке программирования С++.
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к исследованию методов линейного, бинарного и индексно-последовательного поиска;
- ответить на контрольные вопросы и получить оценку по знанию теории;
- получить задание на выполнение конкретного варианта лабораторной работы и выполнить его;
- написать и отладить программу решения задачи на языке С++;
- составить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
Поиск – это действие наиболее часто встречающееся в программировании. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных по мере их появления. Существует несколько основных "вариаций этой темы", и для них создано много различных алгоритмов. При дальнейшем рассмотрении мы исходим из такого принципиального допущения: группа данных, в которой необходимо отыскать заданный элемент, фиксирована. Будем считать, что множество из 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
Эффективность данного вида поиска величина O( ). Данный вид поиска, также как и бинарный, может давать значительный эффект при больших размерах таблиц поиска. Рекомендованный шаг для n элементов таблице – приблизительно . В принципе, для достижения наибольшей эффективности поиска при решении конкретных задач пользователь может задавать какой угодно шаг.
4.5. Контрольные вопросы по теории (линейного и бинарного поиска)
1. Где эффективен линейный поиск?
- в списке;
- в массиве;
- в массиве и в списке.
2. Какой поиск эффективнее?
- линейный;
- бинарный;
- без разницы.
3. В чём суть бинарного поиска ?
- нахождение элемента массива x путём деления массива пополам каждый раз, пока элемент не найден;
- нахождение элемента x путём обхода массива;
- нахождение элемента массива х путём деления массива.
4. Как расположены элементы в массиве бинарного поиска ?
- по возрастанию;
- хаотично;
- по убыванию.
5. В чём суть линейного поиска?
- производится последовательный просмотр от начала до конца и обратно через 2 элемента;
- производится последовательный просмотр элементов от середины таблицы;
- производится последовательный просмотр каждого элемента.
Примеры алгоритмов конкретных задач
Теперь рассмотрим листинги программ на языке С++, реализующие рассмотренные выше виды поиска.
В примерах таблицы поиска содержат только целочисленный ключ, а поля данных отсутствуют. Таблицы поиска задаются в виде одномерных массивов целых чисел (ключей записей).
Функция поиска для элемента по совпадению в неупорядоченной таблице возвращает индекс элемента либо -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;
}
По данному алгоритму на каждом выполняется 2 сравнения.
Пример программы с использованием данной функции будет следующий:
/* ПОИСК ПО СОВПАДЕНИЮ КЛЮЧА */
#include <stdio.h>
#include <conio.h>
#define m 10
int poisk1(int A[],int n,int key);
/* ======================================== */
int main()
{
int i,key,ind, A[m];
printf(" Поиск по совпадению ключа ");
printf("\n Введите %d целых чисел \n",m);
for (i=0; i<m; i++)
scanf("%d",&A[i]);
printf("\n Введите значение искомого ключа =>");
scanf("%d",&key);
printf("\n Поиск элемента по совпадению ");
printf("\n Исходный массив:\n");
for(i=0; i<m; i++)
printf("%5d",A[i]);
ind= poisk1(A,m,key);
if (ind == -1)
printf("\n Элемент %d не найден \n",key);
else printf("\n Элемент %d имеет индекс %d\n",key,ind);
getch(); return 0;
}
/* ========================================== */
/* ФУНКЦИЯ ПОИСКА ЭЛЕМЕНТА ПО СОВПАДЕНИЮ */
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;
}
/* *************************************************** */
Как было сказано выше, для улучшения алгоритма поиска можно использовать заграждающий элемент или барьер. В этом случае последняя запись таблицы запоминается, а после завершения поиска восстанавливается в таблице. В последний элемент массива заносится ключ поиска, и образуется так называемый заграждающий элемент.
Теперь на каждом шаге поиска осуществляется только одно сравнение, а сам поиск продолжается до нахождения элемента с заданным ключом. Если искомого элемента в исходной таблице не было, поиск закончится на барьере. Таким образом, использование барьера в случае числовых ключей существенно сокращает число сравнений. Если ключом поиска является символьная строка, то использование заграждающего элемента вряд ли оправдано.
Приведем пример программы последовательного поиска на С++ с использованием барьера.
/* ************************************************* */
/* ПОИСК ПО СОВПАДЕНИЮ КЛЮЧА - ЗАГРАЖДАЮЩИЙ ЭЛЕМЕНТ */
#include <stdio.h>
#include <conio.h>
#define m 10
int poisk2(int A[],int n,int key);
main()
{
int i,key,ind, A[m];
printf (" Поиск по совпадению ключа ");
printf ("\ n Введите % d целых чисел \ n ", m );
for (i=0; i<m; i++)
scanf("%d",&A[i]);
printf ("\ n Введите значение искомого ключа =>");
scanf ("% d ",& key );
printf ("\ n Поиск элемента по совпадению ");
printf ("\ n Исходный массив:\ n ");
for(i=0; i<m; i++)
printf("%5d",A[i]);
ind= poisk2(A,m,key);
if (ind == -1)
printf("\nЭлемент %d не найден\n",key);
else printf("\n Элемент %d имеет индекс %d\n",key,ind);
getch (); return 0;
}
/* ======================================= */
/* ПОИСК ЭЛЕМЕНТА ПО СОВПАДЕНИЮ С ЗАГРАЖДАЮЩИМ ЭЛЕМЕНТОМ */
int poisk2(int A[],int n,int k)
{ int i = 0;
A[n] = k;
while (A[i] != k )
i++;
return (i == n) ? -1 : i;
}
/* ****************************************************** */
Как было сказано выше, в случае, если последовательность упорядочена по возрастанию (убыванию), можно использовать более эффективные методы поиска. Приведем листинг примера программы, которая осуществляет бинарный поиск в упорядоченной по возрастанию последовательности чисел.
/* ****************************************************** */
/* БИНАРНЫЙ ПОИСК В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ */
#include <stdio.h>
#include <conio.h>
#define m 10
int bisearch(int A[],int n,int key);
int bisearch1(int A[],int n,int key);
/* ======================================== */
/* ГЛАВНАЯ ФУНКЦИЯ */
main()
{ int i,key, A[m];
printf(" Бинарный поиск в упорядоченной таблице ");
printf("\n Введите %d целых чисел в возрастающем порядке\n",m);
for (i=0; i<m; i++)
scanf("%d",&A[i]);
printf("\n Введите значение искомого ключа =>");
scanf("%d",&key);
i = bisearch1(A,m,key);
if (i == -1)
printf(" Ключ %d не найден ",key);
else
printf(" %d- й элемент имеет ключ = %d \n",i,A[i]);
getch();
return 0;
}
/* ========================================= */
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ Вариант 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 в упорядоченной таблице с помощью линейного поиска. Найти числа, большие 50 с помощью бинарного и индексно-последовательного поиска.
7. Найти элемент в упорядоченном массиве А и найти число сравнений помощью линейного, бинарного и индексно-последовательного поиска.
8. Поиск элементов случайным образом помощью линейного, бинарного и индексно-последовательного поиска.
9. Дан список номеров машин (345, 368, 876, 945, 564, 387, 230), найти, на каком месте стоит машина с заданным номером, с помощью линейного поиска. Расположить данные номера в порядке возрастания и решить предыдущую задачу с помощью бинарный и индексно-последовательного поиска.
10. Поиск каждого кратного двум элемента в упорядоченном массиве помощью линейного поиска. Найти данные элементы с помощью бинарного и индексно-последовательного поиска.
11. Найти элемент с ключом, равным сумме индексов упорядоченного массива А с помощью линейного, бинарного и индексно-последовательного поиска.
Дата: 2019-12-10, просмотров: 516.
