ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 9
Тема:
«Исследование методов линейного и бинарного поиска»
Цель: научиться выполнять поиск
искомого значения (ключа) с одномерном массиве с
помощью линейного и бинарного поиска.
Ход работы
Теоретические обоснования
Поиск
–
процесс отыскания информации во множестве данных (обычно представляющих собой
записи) путем просмотра специального поля в каждой записи, называемого ключом.
Целью поиска является отыскание записи (если она есть) с данным значением
ключа.
Поиск
– одно из наиболее часто встречающихся в программировании действий. Существует
множество различных алгоритмов этого действия, принципиально зависящих от
способа организации данных.
При
дальнейшем рассмотрении поиска в линейных структурах определим, что множество
данных, в котором производится поиск, описывается как одномерный массив.
Последовательный
(линейный) поиск
Последовательный
поиск – самый простой из известных.
Суть его заключается в следующем. Множество элементов просматривается последовательно
в некотором порядке, гарантирующем, что будут просмотрены все элементы
множества (например, слева направо). Если в ходе просмотра множества будет
найден искомый элемент, просмотр прекращается с положительным результатом; если
же будет просмотрено все множество, а элемент не будет найден, алгоритм должен
выдать отрицательный результат.
Именно
так поступает человек, когда ищет что-то в неупорядоченном множестве. Таким
образом, данный алгоритм можно применять тогда, когда нет никакой
дополнительной информации о расположении данных в рассматриваемой
последовательности.
Оформим
описанный алгоритм в виде подпрограммы на Си++.
Подпрограмма
выводит результат внутри себя – для этого используем тип подпрограммы void.
void LineSearch(int n, int a[],int b)
{
int i=0;
//пока i не превышает размер массива и
//пока элемент массива не равен ключу
while ((i<n)
&& (a[i]!=b))
{
i++; //наращиваем номер
массива
}
if (i==n) cout<<"Ключ не найден"<<endl;
else if
(i<n)
cout<<"Ключ
находится на "<<i+1<<" позиции"<<endl;
}
Бинарный
поиск
Этот
алгоритм поиска предполагает, что множество хранится, как некоторая упорядоченная
(например, по возрастанию) последовательность элементов, к которым можно
получить прямой доступ посредством индекса. Фактически речь идет о том, что множество
хранится в массиве и этот массив отсортирован.
Суть
метода заключается в следующем. Областью поиска (L, R) назовем часть массива с
индексами от L до R, в которой предположительно находится искомый элемент.
Сначала областью поиска будет часть массива (L, R), где L = 1, а R = n, т. е. вся заполненная элементами множества часть
массива. Теперь найдем индекс среднего элемента m := (L+R) div 2. Если Key > А[m], то можно
утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из
элементов с индексами от L + m до R, следовательно,
можно присвоить L := m + 1,
сократив область поиска. В противном случае можно положить R
:= m. На этом заканчивается первый шаг метода.
Остальные шаги аналогичны (рис. 1).
На
каждом шаге метода область поиска будет сокращаться вдвое. Как только L станет
равно R, т. е. область поиска сократится до одного элемента, можно будет
проверить этот элемент на равенство искомому и сделать вывод о результате
поиска.
Задание 1. Выполнить
линейный поиск ключа в одномерном массиве. Ввод, вывод массива и поиск
осуществить в виде подпрограммы.
Задание 2. Выполнить
бинарный поиск ключа в одномерном массиве. Осуществить ввод, вывод, сортировку массива
и поиск в массиве.
Выполнение
задания 1.
#include <iostream.h>
#include <iomanip.h>
#include <ctime>
//подпрограмма ввода массива
//параметрами являются размер массива и массив
void vvod(int
n, int a[]);
//подпрограмма вывода массива на экран
void
vivod(int
n, int a[]);
//подпрограмма линейного поиска в массиве
//параметрами являются размер массива, массив, ключ для поиска
int LineSearch(int n, int a[],int b);
//главная программа
int main()
{
system("chcp 1251>nul");
//описываем динамический массив, размер массива и
//переменную для работы с
массивом
int n,*a, i;
cout<<"Введите
размер массива n=";
cin>>n;
//выделение памяти под массив
a=new int [n];
//вызов подпрограммы
заполнения массива
vvod(n,a);
//вызов подпрограммы вывода
массива
vivod(n,a);
int b; //ключ
i=0; //"становимся"
на первый элемент массива
cout<<"Введите
ключ "; cin>>b;
//вызов подпрограммы поиска
LineSearch(n,a,b);
//освобождение памяти от
массива
delete[] a;
system("pause");
return 0;
}
//реализация подпрограммы ввода массива
void vvod(int
n, int a[])
{
int a1,b1,i;
cout<<"Введите
диапазон заполнения массива: ";
cin>>a1>>b1;
cout<<"Исходный
массив:"<<endl;
srand(time(NULL));
for(i=0; i<n;
i++)
{
a[i]=(b1-a1)*rand()/32767+a1;
}
};
//реализация подпрограммы вывода массива
void vivod(int
n, int a[])
{
int i;
for(i=0; i<n;
i++)
{
cout<<setw(5)<<a[i];
}
cout<<endl;
};
//реализация подпрограммы линейного поиска
void LineSearch(int n, int a[],int b)
{
//пока i не превышает размер массива и
//пока элемент массива не
равен ключу
int i=0;
while ((i<n) && (a[i]!=b))
{
i++; //наращиваем
номер массива
}
if (i==n) cout<<"Ключ
не найден"<<endl;
else
if (i<n)
cout<<"Ключ
находится на "<<i+1<<" позиции"<<endl;
}
Выполнение
задания 2.
#include <iostream.h>
#include <iomanip.h>
#include <ctime>
//подпрограмма бинарного поиска
int BinarySearch(int a[], int b, int n);
int main()
{
system("chcp 1251>nul");
int a1,b1,n,i,*a;
cout<<"Введите размер массива n=";
cin>>n;
a=new
int [n];
cout<<"Введите диапазон заполнения массива: ";
cin>>a1>>b1;
cout<<"Исходный
массив:"<<endl;
srand(time(NULL));
//заполнение
и вывод массива
for(i=0; i<n; i++)
{
a[i]=(b1-a1)*rand()/32767+a1;
cout<<setw(5)<<a[i];
}
cout<<endl;
//сортировка
//...
//бинарный
поиск
int
b,m; //ключ, номер середины массива
cout<<"Введите
ключ "; cin>>b;
cout<<"b="<<b<<endl;
int k=BinarySearch(a,
b, n);
if (k!=-1) cout<<"Ключ находится на
"<<k+1<<" позиции"<<endl;
else cout<<"Ключ не
найден"<<endl;
//освобождение
памяти от массива
delete[]
a;
system("pause");
return
0;
};
//реализация подпрограммы бинарного поиска
int BinarySearch(int a[], int b, int n)
{
int m;
int left=0, right=n-1;
while (left <=right)
{
m
= (left + right) / 2;
if (b < a[m])
right = m - 1;
else if (b > a[m])
left = m + 1;
else return m;
}
if (left >= right) return -1;
}
Решить самостоятельно:
ЗАДАНИЕ 1
Решить
задачу согласно своему варианту. Заполнение, вывод и поиск осуществить в виде
подпрограммы.
ЗАДАНИЕ 2