Binary search benchmark

binary_search_benchmark.cpp

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
#include <iomanip>

// Perform a simple linear search
int64_t linear_search(const std::vector<int64_t>& array, const int64_t search)
{
    for (int64_t i = 0; i < array.size(); i++)
        if (array[i] == search)
            return i;
    return -1;
}

int64_t binary_search(const std::vector<int64_t>& array, const int64_t search)
{
    int64_t lower = 0;
    auto higher = static_cast<int64_t>(array.size() - 1);

    while (lower <= higher)
    {
        const int64_t middle = lower + (higher - lower) / 2;

        if (array[middle] == search)
            return middle;

        if (array[middle] < search)
            lower = middle + 1;
        else
            higher = middle - 1;
    }

    return -1;
}

int main() {
    std::cout << "Size,Linear Search (nanoseconds),Binary Search (nanoseconds)\n";

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int64_t> dist(1, 1'000'000'000);

    // Test array
    const std::vector<size_t> sizes =
    {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100,
        102, 105, 107, 110, 112, 114, 116, 118, 120, 122, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200,

        500, 1'000, 5'000, 10'000,
        50'000, 100'000, 500'000, 1'000'000, 5'000'000,
        10'000'000, 100'000'000, 500'000'000
    };

    for (const size_t n : sizes)
    {
        std::vector<int64_t> data(n);
        for (size_t i = 0; i < n; ++i)
            data[i] = dist(gen);
        std::ranges::sort(data);

        const int64_t target = dist(gen);

        constexpr int64_t trials = 10'0;
        int64_t linear_total = 0;
        int64_t binary_total = 0;

        for (int64_t t = 0; t < trials; ++t)
        {
            // Measure linear search
            auto start = std::chrono::high_resolution_clock::now();
            linear_search(data, target);
            auto end = std::chrono::high_resolution_clock::now();
            linear_total += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

            // Measure binary search
            start = std::chrono::high_resolution_clock::now();
            binary_search(data, target);
            end = std::chrono::high_resolution_clock::now();
            binary_total += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }

        const long double linear_avg = static_cast<long double>(linear_total) / trials;
        const long double binary_avg = static_cast<long double>(binary_total) / trials;

        std::cout << n << "," << std::fixed << std::setprecision(10) << linear_avg << "," << binary_avg << "\n";
    }

    return 0;
}