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

Реализация линейного и бинарного поиска в C++

Цель работы: Научиться реализовывать алгоритмы линейного и бинарного поиска в массиве целых чисел на языке C++, сравнивать их работу, понимать алгоритмические различия и ограничения.

1. Линейный поиск

Линейный поиск — самый простой алгоритм поиска, при котором массив просматривается последовательно от начала к концу, и каждый элемент сравнивается с искомым значением.

Кратко о принципе:

Применим к любым (неупорядоченным) массивам.
Сложность: $ O(n) $.
Если элемент найден — возвращается его индекс, иначе — «не найден».

Пример кода:

int linearSearch(const int* arr, int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i; // возвращаем индекс найденного элемента
        }
    }
    return -1; // не найден
}

2. Бинарный поиск

Бинарный поиск применяется только к заранее отсортированным массивам. Алгоритм делит диапазон поиска пополам, сравнивает центральный элемент с искомым, и по этому результату сужает область поиска.

Кратко о принципе:

Требует отсортированный массив.
Сложность: $ O(\log n) $.
Если элемент найден — возвращается его индекс, иначе — «не найден».

Пример кода:

int binarySearch(const int* arr, int size, int key) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        else if (arr[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1; // не найден
}

Компиляция и запуск программы

g++ *имя_файла*.cpp -o *название_файла_для_компиляции*

./*название_скомпилированного_файла*

Общие требования

Для каждого алгоритма реализовать отдельную функцию.
Провести поиск заданного элемента двумя способами, вывести результаты.
Реализовать проверки на успешное/неуспешное завершение поиска.
Использовать тестовые данные.
По желанию: провести сравнение времени работы (через $ std::chrono $).

Задания для выполнения

Выбор варианта: Номер варианта соответствует порядковому номеру студента в списке группы. Если количество студентов превышает 7, варианты повторяются по кругу (например, 8-й студент выполняет Вариант 1, 9-й - Вариант 2 и т.д.).

Вариант 1

№	Задача	Описание
1	Линейный поиск	Заполнить массив из 20 элементов случайными числами от 1 до 50. Запросить у пользователя число, найти его с помощью линейного поиска, вывести индексы всех вхождений, либо «не найдено».
2	Бинарный поиск	Отсортировать тот же массив, повторно запросить число, выполнить бинарный поиск, вывести индекс одного из вхождений, либо «не найдено».
3	Сравнение	Сравнить поведение алгоритмов (решение, сколько сравнений было произведено каждым алгоритмом).

Вариант 2

№	Задача	Описание
1	Линейный поиск	Пользователь вводит массив из 15 целых чисел вручную. Запросить число для поиска, вывести индекс(-ы) всех вхождений, либо сообщение «не найдено».
2	Бинарный поиск	Отсортировать массив, выполнить бинарный поиск заданного числа, вывести индекс первого найденного элемента, либо «не найдено».
3	Пояснение	В пояснении добавить: почему бинарный поиск работает только на отсортированном массиве.

Вариант 3

№	Задача	Описание
1	Линейный поиск - отсутствующий элемент	Создать массив из 10 чисел (ручной ввод или случайные), попробовать найти элемент, не входящий в массив (например, 100). Описать результат линейного поиска.
2	Бинарный поиск - отсутствующий элемент	Отсортировать массив и выполнить бинарный поиск такого же отсутствующего элемента, отразить результат.
3	Тест	Провести тест с элементом в начале, середине и конце массива для обоих методов. Объяснить различия.

Вариант 4

№	Задача	Описание
1	Линейный поиск (несколько вхождений)	Заполнить массив из 30 чисел случайными значениями, добавить несколько одинаковых элементов. Найти число с помощью линейного поиска, вывести все индексы.
2	Бинарный поиск (одно вхождение)	После сортировки, выполнить бинарный поиск, вывести индекс одного из найденных элементов.
3	Консультация	Описать, почему бинарный поиск не позволяет найти все одинаковые элементы — только один из них.

Вариант 5

№	Задача	Описание
1	Линейный поиск — текст	Вводится массив строк (например, имена). Реализовать линейный поиск по строковому массиву, вывести все совпадения.
2	Бинарный поиск — числа	Для массива из 25 целых чисел реализовать бинарный поиск после сортировки.
3	Вывод	Сравнить сущность поиска в числовом и строковом массиве.

Вариант 6

№	Задача	Описание
1	Линейный поиск — отрицательные числа	Заполнить массив из 15 чисел с отрицательными значениями. Найти заданное отрицательное число, вывести индекс(-ы).
2	Бинарный поиск	Отсортировать массив (по возрастанию) и выполнить бинарный поиск того же числа.
3	Замечание	Доказать на примере, что бинарный поиск не работает на неотсортированных данных.

Вариант 7

№	Задача	Описание
1	Линейный поиск (ручной ввод)	Пользователь вводит массив из 10 чисел с клавиатуры. Найти число, заданное с клавиатуры, вывести его индекс(-ы), либо «не найдено».
2	Бинарный поиск (отсортированный ввод)	После ручной сортировки, выполнить бинарный поиск по тому же массиву.
3	Сравнение	Кратко — сравнить, в каких случаях эффективнее использовать бинарный поиск.

Контрольные вопросы

В чем принципиальное отличие линейного поиска от бинарного поиска?
Почему бинарный поиск не может быть применен к неотсортированному массиву?
Каковы временные сложности алгоритмов поиска и что это значит на практике?
Приведите пример массива, когда бинарный поиск работает быстрее линейного поиска.
Могут ли оба метода найти все одинаковые элементы? Почему?
Какие ограничения есть у бинарного поиска?
Как проверить корректность работы программы поиска?