#include <iostream>
#include <vector>
#include <chrono>

// Binary search function
bool binary_search(const std::vector<int>& arr, int target) {
    int left = 0;                      // Starting index of the search range
    int right = arr.size() - 1;        // Ending index of the search range
    
    // While the search range is valid (left <= right)
    while (left <= right) {
        // Calculate the middle index to avoid overflow
        int middle = left + (right - left) / 2;
        
        // If the middle element is the target, return true (found)
        if (arr[middle] == target) {
            return true;
        }
        // If the target is larger, ignore the left half
        else if (arr[middle] < target) {
            left = middle + 1;
        }
        // If the target is smaller, ignore the right half
        else {
            right = middle - 1;
        }
    }
    return false;  // Target not found
}

int main() {
    // Sizes of the arrays
    std::vector<int> sizes = {100, 400, 1600, 6400, 25600, 102400, 409600, 1638400};
    
    // Loop through each array size in the 'sizes' vector
    for (int size : sizes) {
        std::vector<int> arr(size);
        for (int i = 0; i < size; ++i) {
            arr[i] = i;
        }
        
        // Capture the start time for the search operation
        auto start = std::chrono::high_resolution_clock::now();
        
        // Perform 20 million unsuccessful binary search operations (for consistency)
        for (int i = 0; i < 20000000 ; ++i) {
            binary_search(arr, -1);  // Search for a value not present in the array
        }
        
        // Capture the end time for the search operation
        auto end = std::chrono::high_resolution_clock::now();
        
        // Calculate the total elapsed time
        std::chrono::duration<double> elapsed = end - start;
        
        // Print the array size and the time taken
        std::cout << "Array size: " << size << ", Time: " << elapsed.count() << " seconds" << std::endl;
    }
    
    return 0;
}