Файл: Практическая работа 5 Алгоритм поиска в отсортированных массивах Постановка задачи.docx

Каширский Герман Владимирович

ИКБО-21-22

Практическая работа № 5

Алгоритм поиска в отсортированных массивах
Постановка задачи

Составить программу поиска заданного элемента по ключу в одномерном целочисленном массиве A[n], используя алгоритм согласно варианту индивидуального задания. Провести тестирование программы на исходном массиве, сформированном вводом с клавиатуры. Рабочий массив A сформировать с использованием генератора псевдослучайных чисел. Провести контрольные прогоны программы для размеров массива n = 100, 1000, 10000, 100000 и 1000000 элементов в трех режимах: на массивах, строго убывающих, строго возрастающих и случайных чисел и сделать вывод о зависимости (устойчивости) алгоритма от исходной упорядоченности массива.

Провести эмпирическую (практическую) оценку вычислительной сложности алгоритма, для чего предусмотреть в программе подсчет фактического количества операций сравнения Сф.

Полученные результаты свести в сводную таблицу. Построить в одной координатной плоскости графики зависимости теоретической О(n)=f(С(n)) и эмпирической (Сф(n)) вычислительной сложности алгоритма от количества элементов в массиве n.

Сравнить вычислительную сложность алгоритма с вычислительной сложностью алгоритма последовательного поиска. Экспериментально оценить долю случаев, когда последовательный поиск выполняется быстрее, чем быстрый поиск.

Провести анализ полученных результатов. Сделать выводы о проделанной работе, основанные на полученных результатах.
Сводная таблица результатов

n	f(C)	Cф
100	6.64	18
1000	9.97	27
10000	13.28	36
100000	16.61	45

---

#include

#include

#include
using namespace std;
int main() {

int n;

cout << "Enter the size of the array = ";

cin >> n;

int* arr = new int[n]; // создали динамический массив

int key; // создали переменную в которой будет находиться ключ

int cf = 0;

for (int i = 0; i < n; i++) {

arr[i] = rand(); // записываем массив рандомными числами

}
sort(arr, arr + n); // сортируем с помощью функции sort (быстрая сортировка)

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";

}

cout << endl << "Enter the key: ";
cin >> key; // считываем ключ
bool flag = false;

int l = 0; // левая граница

int r = n - 1; // правая граница

int mid;
while ((flag != true)) {

mid = (l + r) / 2; // считываем срединный индекс отрезка [l,r]
if (arr[mid] == key) { flag = true; } //проверяем ключ со серединным элементом

if (arr[mid] > key) { r = mid - 1; } // проверяем, какую часть нужно отбросить

if (arr[mid] < key) { l = mid + 1; }

cf += 3;

}
if (flag) cout << "Element index " << key << " in the array is equal to: " << mid << endl;

else cout << "Sorry, but there is no such element in the array" << endl;

cout << "cf = " << cf;

system("pause");

return 0;

}

---