graph

import java.util.Arrays;

/**
 * Benchmark for the performance of iterative and recursive binary search algorithms.
 * It measures execution time and approximates memory usage for various dataset sizes.
 */
public class BinarySearchBenchmark {

    /**
     * The main method that runs the benchmarks for iterative and recursive binary search algorithms
     * for different dataset sizes.
     *
     * @param args Command line arguments (not used)
     */
    public static void main(String[] args) {
        long[] dataset = new long[200_000];
        for (long i = 0; i < dataset.length; i++) {
            dataset[(int) i] = i;
        }

        long[] testSizes = {1_000_000, 2_000_000, 3_000_000, 4_000_000, 5_000_000, 6_000_000, 7_000_000, 8_000_000,
                9_000_000, 10_000_000, 20_000_000, 30_000_000, 40_000_000, 50_000_000, 60_000_000,
                70_000_000, 80_000_000, 90_000_000, 100_000_000, 200_000_000, 300_000_000,
                400_000_000, 500_000_000, 600_000_000, 700_000_000, 800_000_000, 900_000_000,
                1_000_000_000};

        System.out.printf("%-15s %-20s %-20s %-20s %-20s%n",
                "Input Size (n)", "Iterative Time (ns)", "Recursive Time (ns)",
                "Iterative Memory (bytes)", "Recursive Memory (bytes)");

        for (long size : testSizes) {
            long[] subDataset = Arrays.copyOf(dataset, (int) size);
            long target = subDataset[(int) (size / 2)];

            long iterativeTime = benchmark(() -> iterativeBinarySearch(subDataset, target));
            long iterativeMemoryUsed = measureIterativeMemoryUsage(subDataset);

            long recursiveTime = benchmark(() -> recursiveBinarySearch(subDataset, 0, subDataset.length - 1, target));
            long recursiveMemoryUsed = measureRecursiveMemoryUsage(subDataset);

            System.out.printf("%-15d %-20d %-20d %-20d %-20d%n",
                    size,
                    iterativeTime,
                    recursiveTime,
                    iterativeMemoryUsed,
                    recursiveMemoryUsed);
        }
    }

    /**
     * Performs the iterative binary search on the given array.
     *
     * @param array  The array on which the search is performed
     * @param target The target number to search for
     */
    private static void iterativeBinarySearch(long[] array, long target) {
        long low = 0, high = array.length - 1;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (array[(int) mid] == target) return;

            if (array[(int) mid] < target) low = mid + 1;
            else high = mid - 1;
        }
    }

    /**
     * Performs the recursive binary search on the given array.
     *
     * @param array  The array on which the search is performed
     * @param low    The lowest index of the search range
     * @param high   The highest index of the search range
     * @param target The target number to search for
     * @return The index of the target number, or -1 if not found
     */
    private static int recursiveBinarySearch(long[] array, long low, long high, long target) {
        if (low > high) return -1;
        long mid = low + (high - low) / 2;
        if (array[(int) mid] == target) return (int) mid;

        if (array[(int) mid] < target) return recursiveBinarySearch(array, mid + 1, high, target);
        return recursiveBinarySearch(array, low, mid - 1, target);
    }

    /**
     * Measures the time it takes to run the given search function.
     *
     * @param search The search function to measure
     * @return The time in nanoseconds
     */
    private static long benchmark(Runnable search) {
        long startTime = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            search.run();
        }
        return System.nanoTime() - startTime;
    }

    /**
     * Measures the memory usage during the execution of the given search function for the iterative binary search.
     *
     * @param array The array on which the search is performed
     * @return The memory usage in bytes
     */
    private static long measureIterativeMemoryUsage(long[] array) {
        System.gc();
        long beforeMemory = getUsedMemory();
        iterativeBinarySearch(array, array[0]);
        long afterMemory = getUsedMemory();

        long arrayMemory = (long) array.length * Long.BYTES;
        long overheadMemory = 3 * Long.BYTES;

        return (afterMemory - beforeMemory) + arrayMemory + overheadMemory;
    }

    /**
     * Measures the memory usage during the execution of the given search function for the recursive binary search.
     *
     * @param array The array on which the search is performed
     * @return The memory usage in bytes
     */
    private static long measureRecursiveMemoryUsage(long[] array) {
        System.gc();
        int depth = (int) (Math.log(array.length) / Math.log(2));
        long stackMemoryPerFrame = 128;

        return depth * stackMemoryPerFrame;
    }

    /**
     * Gets the used memory in the JVM in bytes.
     *
     * @return The used memory in bytes
     */
    private static long getUsedMemory() {
        return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
    }
}