Линейный и бинарный поиск

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Кафедра безопасности информационных систем

ОТЧЁТ

по практической работе работе №4 на тему:
«Линейный и бинарный поиск»

по дисциплине «Алгоритмы и структуры данных»

Выполнил: студент группы XXX

«xx» XXX 20xx г. ___________/XXX/

Принял: XXX

«xx» XXX 20xx г. ___________/ XXX /

СОДЕРЖАНИЕ

1. Цель работы        4

2. Результаты выполнения работы        4

ЗАКЛЮЧЕНИЕ        8

1. Цель работы

Изучение и применение на языке среднего уровня C++ двух методов поиска: линейный и бинарный. Оценка трудоёмкости данных методов

1. Результаты выполнения работы

Для достижения цели работы, создана программа для поиска некоторого числа в массиве из 30 элементов с помощью двух методов поиска.

Первый метод — линейный. Данный метод поиска основан на сравнение ключевого числа со всеми элементами массива по порядку, начиная с первого. Так как алгоритм сравнивает почти все элементы с ключевым числом, то поиск числа в большом массиве будет нецелесообразен, ввиду его малой скорости поиска. Трудоёмкость данного алгоритма — O(n)

Второй метод для изучения — бинарный поиск. Такой метод поиска более сложен, но наиболее эффективен, чем линейный поиск. Его особенность — поиск ключевого числа методом дробления массива на половины с дальнейшим рекурсивным поиском в одной из них. Правда есть один недостаток — требуется заранее отсортировать массив по убыванию или возрастанию, иначе такой метод не даст положительный результат. Трудоёмкость данного метода — log2(n)

[pic 1]

Рисунок 1 — Положительный исход работы

[pic 2]

Рисунок 2 — Значение в массиве не найдено

Листинг программы:

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

    setlocale(LC_ALL, "rus");

    const int SIZE = 30;

    int A[SIZE], key, count = 0;

    ifstream X("Массив.txt");

    cout << "Изначальный массив:" << endl;

    for (int i = 0; i < SIZE; i++)

    {

        X >> A[i];

        cout << A[i] << " ";

    }

    /*Линейный поиск*/

    cout << endl << endl << "Введите значение для поиска: ";

    cin >> key;

    for (int i = 0; i < SIZE; i++)

    {

        count++;

        if (A[i] == key)

        {

            cout << endl << "Линейный поиск выполнен успешно!" << endl << "Найденный элемент: A[" << i << "] = " << A[i] << endl;