fork download
copy 
  1. #include <iostream>
  2. #include <ctime>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. double* binary_search8(double* arr, const double& x)
  7. {
  8.   if (x<arr[4]) {
  9.     if(x<arr[2]) {
  10.       if(x<arr[1]) {  
  11.         return arr;
  12.       } else {
  13.         return arr + 1;
  14.       }
  15.     }
  16.     else { //2..3
  17.       if(x<arr[3]){  
  18.         return arr + 2;
  19.       } else {
  20.         return arr + 3;
  21.       }
  22.     }
  23.   } else { // 4..7
  24.     if(x<arr[6]) {
  25.       if(x<arr[5]) {  
  26.         return arr + 4;
  27.       } else {
  28.         return arr + 5;
  29.       }
  30.     } else { //6..7
  31.       if(x<arr[7]) {  
  32.         return arr + 6;
  33.       } else {
  34.         return arr + 7;
  35.       }
  36.     }
  37.   }
  38. }
  39.  
  40.  
  41. double* binary_search16(double* arr, const double& x)
  42. {
  43. 	if (x<arr[8]) return binary_search8(arr, x);
  44. 	else return binary_search8(arr+8, x);
  45. }
  46.  
  47. int main() {
  48. double test[16] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150};
  49.  
  50.   vector<double> test_vals;
  51.   size_t num_elem = 10000000;
  52.   for (size_t i=0; i<num_elem; i++)
  53.     test_vals.push_back(rand()%150);
  54.  
  55.   clock_t begin, end;
  56.   double elapsed_secs;
  57.  
  58.   // Linear search
  59.   double linavg = 0;
  60.   begin = clock();
  61.   for (size_t i=0; i<num_elem; i++) {   
  62.     linavg += *(find_if(test, test+16, bind2nd(std::greater_equal<double>(), test_vals[i]))-1);
  63.   }
  64.   end = clock();
  65.   elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
  66.   cout << "linear secs: " <<elapsed_secs << ", testval = " << linavg << std::endl;
  67.  
  68.  
  69.   // Binary search
  70.   double binavg = 0;
  71.   begin = clock();
  72.   for (size_t i=0; i<num_elem; i++) {
  73.     binavg += *binary_search16(test, test_vals[i]);
  74.   }
  75.   end = clock();
  76.   elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
  77.   cout << "binary secs: " <<elapsed_secs << ", testval = " << binavg << std::endl;
  78.  
  79.   // Binary search 2
  80.   double binavg2 = 0;
  81.   begin = clock();
  82.   for (size_t i=0; i<num_elem; i++) {
  83.     binavg2 += *(std::upper_bound(test, test+16, test_vals[i])-1);
  84.   }
  85.   end = clock();
  86.   elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
  87.   cout << "binary2 secs: " <<elapsed_secs << ", testval = " << binavg2 << std::endl;
  88.  
  89.   return 0;
  90. }
Success #stdin #stdout 1.6s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
linear secs: 0.31, testval = 6.9063e+08
binary secs: 0.39, testval = 6.99953e+08
binary2 secs: 0.42, testval = 6.99953e+08
https://ideone.com/Fo5ZeW
language:
C++14 (gcc 8.3)
created:
10 years 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!