lab01/task1_poisk.cpp - master - Konst_And/Labs_cpp

lab01/task1_poisk.cpp
142 строки5 KB
And Konst
move files
05 мар 2026, 14:57
05 мар 2026, 14:57dc5b7a2
#include <iostream>
#include <chrono>
#include <random>

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Задание 1: поиск

bool lin(int* arr, int size, int key) { // линейный поиск
    for (int i = 0; i < size; ++i) {
        if (arr[i] == key)
            return true;
    }
    return false;
}

bool bin(int* arr, int size, int key) { // бинарный поиск
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key)
            return true;
        if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return false;
}

void task1() {
    std::cout << "\nЗадание 1: поиск\n";
    std::default_random_engine rng(1001);
    std::uniform_int_distribution<int> dist(0, 1700000);
    std::uniform_int_distribution<int> missing_dist(1700001, 2000000);  // для несуществующих

    std::cout << "N\t\tЛин ср\tЛин худ\tБин ср\tБин худ\n";

    for (int N = 100; N <= 1700000; N *= 2) {
        int* arr_unsort = new int[N];
        for (int i = 0; i < N; ++i)
            arr_unsort[i] = dist(rng);
        
        int* arr_sort = new int[N];
        for (int i = 0; i < N; ++i)
            arr_sort[i] = i * 2;
        
        // Худший случай
        int key_worst = 2000001;  // число больше максимального
        
        // линейный поиск - наихудший
        int lin_iter = 1000; 
        int notopt_lin_wor = 0;
        auto begin = std::chrono::steady_clock::now();
        for (int iter = 0; iter < lin_iter; ++iter) {
            notopt_lin_wor += lin(arr_sort, N, key_worst);
        }
        auto end = std::chrono::steady_clock::now();
        auto lin_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double lin_worst = static_cast<double>(lin_total) / lin_iter;
        
        // бинарный поиск - наихудший
        int bin_iter = 100000; 
        int notopt_bin_wor = 0;
        begin = std::chrono::steady_clock::now();
        for (int iter = 0; iter < bin_iter; ++iter) {
            notopt_bin_wor += bin(arr_sort, N, key_worst);
        }
        end = std::chrono::steady_clock::now();
        auto bin_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double bin_worst = static_cast<double>(bin_total) / bin_iter;
        
        // Средний случай
        
        // линейный поиск - средний
        int lin_avg_iter = 1000;
        int notopt_lin_avg = 0;
        begin = std::chrono::steady_clock::now();
        for (int iter = 0; iter < lin_avg_iter; ++iter) {
            int key_avg;
            if (iter % 2 == 0) {
                // Четные итерации - существующий ключ
                int random_index = rng() % N;
                key_avg = arr_unsort[random_index];
            } else {
                // Нечетные итерации - несуществующий ключ
                key_avg = missing_dist(rng);
            }
            notopt_lin_avg += lin(arr_unsort, N, key_avg);
        }
        end = std::chrono::steady_clock::now();
        lin_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double lin_avg = static_cast<double>(lin_total) / lin_avg_iter;
        
        // бинарный поиск - средний
        int bin_avg_iter = 100000;
        int notopt_bin_avg = 0;
        begin = std::chrono::steady_clock::now();
        for (int iter = 0; iter < bin_avg_iter; ++iter) {
            int key_avg;
            if (iter % 2 == 0) {
                // Четные итерации - существующий ключ
                int random_index = rng() % N;
                key_avg = arr_sort[random_index];
            } else {
                // Нечетные итерации - несуществующий ключ
                key_avg = missing_dist(rng);
            }
            notopt_bin_avg += bin(arr_sort, N, key_avg);
        }
        end = std::chrono::steady_clock::now();
        bin_total = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();
        double bin_avg = static_cast<double>(bin_total) / bin_avg_iter;

        // чтобы не оптимизировал
        int notopt = notopt_lin_wor + notopt_bin_wor + notopt_lin_avg + notopt_bin_avg;
        if (notopt == 123456789) {
            std::cout << "Это никогда не выполнится\n";
        }

        std::cout << N << "\t\t"
                  << lin_avg << "\t\t"
                  << lin_worst << "\t\t"
                  << bin_avg << "\t\t"
                  << bin_worst << "\n";

        delete[] arr_unsort;
        delete[] arr_sort;
    }
}


// main

int main() {
    task1();
    return 0;
}