fork(1) download
copy 
  1.  
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <ctime>
  5.  
  6. using namespace std;
  7.  
  8. const int sz = 10000000;
  9.  
  10. int arr[sz];
  11. int X, pos;
  12.  
  13. bool check(int index, int X) {
  14.     if (index <= 0) {
  15.         return arr[index] == X;
  16.     }
  17.     return (arr[index] == X) && (arr[index - 1] != X);
  18. }
  19.  
  20. int binarySearch(int *arr, int X) {
  21.     int result = -1;
  22.     int l = 0, r = sz - 1;
  23.     int mid;
  24.  
  25.     while (l <= r) {
  26.         mid = (l + r) / 2;
  27.         if (X <= arr[mid]) {
  28.             if (arr[mid] == X) result = mid;
  29.             r = mid - 1;
  30.         } else {
  31.             l = mid + 1;
  32.         }
  33.     }
  34.  
  35.     return result;
  36. }
  37.  
  38. int main(){
  39.     for (int i=0; i<sz; i++) arr[i] = i;
  40.  
  41.     int startTime = time(0);
  42.     for (int t=0; t<10000; t++) {
  43.         X = arr[rand() % sz];
  44.         pos = binarySearch(arr, X);
  45.  
  46.         if (!check(pos, X)) {
  47.             cout<<"FAILED";
  48.         }
  49.     }
  50.     cout<<"Total time for search: "<<(time(0) - startTime)<<"(s)";
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.02s 42692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Total time for search: 0(s)
https://ideone.com/bebfos
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

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!