fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <chrono>
  4.  
  5. // Binary search function
  6. bool binary_search(const std::vector<int>& arr, int target) {
  7.     int left = 0;                      // Starting index of the search range
  8.     int right = arr.size() - 1;        // Ending index of the search range
  9.  
  10.     // While the search range is valid (left <= right)
  11.     while (left <= right) {
  12.         // Calculate the middle index to avoid overflow
  13.         int middle = left + (right - left) / 2;
  14.  
  15.         // If the middle element is the target, return true (found)
  16.         if (arr[middle] == target) {
  17.             return true;
  18.         }
  19.         // If the target is larger, ignore the left half
  20.         else if (arr[middle] < target) {
  21.             left = middle + 1;
  22.         }
  23.         // If the target is smaller, ignore the right half
  24.         else {
  25.             right = middle - 1;
  26.         }
  27.     }
  28.     return false;  // Target not found
  29. }
  30.  
  31. int main() {
  32.     // Sizes of the arrays
  33.     std::vector<int> sizes = {100, 400, 1600, 6400, 25600, 102400, 409600, 1638400};
  34.  
  35.     // Loop through each array size in the 'sizes' vector
  36.     for (int size : sizes) {
  37.         std::vector<int> arr(size);
  38.         for (int i = 0; i < size; ++i) {
  39.             arr[i] = i;
  40.         }
  41.  
  42.         // Capture the start time for the search operation
  43.         auto start = std::chrono::high_resolution_clock::now();
  44.  
  45.         // Perform 20 million unsuccessful binary search operations (for consistency)
  46.         for (int i = 0; i < 20000000 ; ++i) {
  47.             binary_search(arr, -1);  // Search for a value not present in the array
  48.         }
  49.  
  50.         // Capture the end time for the search operation
  51.         auto end = std::chrono::high_resolution_clock::now();
  52.  
  53.         // Calculate the total elapsed time
  54.         std::chrono::duration<double> elapsed = end - start;
  55.  
  56.         // Print the array size and the time taken
  57.         std::cout << "Array size: " << size << ", Time: " << elapsed.count() << " seconds" << std::endl;
  58.     }
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 3.94s 9868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Array size: 100, Time: 0.23619 seconds
Array size: 400, Time: 0.303453 seconds
Array size: 1600, Time: 0.389763 seconds
Array size: 6400, Time: 0.444286 seconds
Array size: 25600, Time: 0.546855 seconds
Array size: 102400, Time: 0.598762 seconds
Array size: 409600, Time: 0.691319 seconds
Array size: 1638400, Time: 0.741596 seconds
https://ideone.com/z3ucYC
language:
C++ (gcc 8.3)
created:
85 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!