Skip to content
The Chat Archive
gpt-4-0314· OpenAI WildChat-4.8M (AI2)

C++ . Задача: Программа реализующая алгоритм бинарного поиска в списке строк, заданном…

  1. User

    C++ . Задача: Программа реализующая алгоритм бинарного поиска в списке строк, заданном пользователем. Напиши код этой программы. Добавь проверку введенных значений. Добавь в код подробные комментарии на русском языке.

  2. Assistant
    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    
    // Функция бинарного поиска
    int binarySearch(std::vector<std::string>& list, std::string value) {
        int left = 0;
        int right = list.size() - 1;
    
        // Делаем поиск, пока левая граница не станет больше правой
        while (left <= right) {
            // Находим средний элемент в текущем отрезке
            int middle = (left + right) / 2;
    
            // Если средний элемент равен искомому значению, возвращаем его индекс
            if (list[middle] == value)
                return middle;
    
            // Если значение среднего элемента меньше искомого значения,
            // значит искомое значение находится в правой половине, иначе в левой
            if (list[middle] < value)
                left = middle + 1;
            else
                right = middle - 1;
        }
    
        // Если значение не найдено, возвращаем -1
        return -1;
    }
    
    
    
    
    int main() {
        // Ввод количества элементов в списке
        int n;
        std::cout << "Введите количество элементов в списке: ";
        std::cin >> n;
    
        // Если введено некорректное значение, завершаем программу
        if (n <= 0) {
            std::cout << "Некорректное количество элементов!" << std::endl;
            return 1;
        }
    
        // Ввод списка строк
        std::vector<std::string> list(n);
        std::cout << "Введите " << n << " строки:" << std::endl;
        for (int i = 0; i < n; i++) {
            std::cin >> list[i];
        }
    
        // Сортируем список строк
        std::sort(list.begin(), list.end());
    
        // Ввод искомого значения
        std::string value;
        std::cout << "Введите искомое значение: ";
        std::cin >> value;
    
        // Выполняем бинарный поиск
        int result = binarySearch(list, value);
    
        // Выводим результат
        if (result == -1) {
            std::cout << "Значение не найдено!" << std::endl;
        } else {
            std::cout << "Значение найдено на позиции: " << result << std::endl;
        }
    
        return 0;
    }
    

    Вот программа на C++, которая реализует алгоритм бинарного поиска в списке строк, заданном пользователем. В коде присутствуют комментарии на русском языке, объясняющие работу программы и алгоритма.