Misha_

Fucking search

Nov 3rd, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int binary_search(int *a, int x, int l, int r) {
  5.     while (l < r) {
  6.         int c = (l+r)/2;
  7.  
  8.         cout << a[c] <<" ";
  9.         if (a[c] == x) {
  10.             return c;
  11.             break;
  12.         }
  13.         if (a[c] > x)
  14.             r = c;
  15.         else
  16.             l = c+1;
  17.     }
  18.     return -1;
  19. }
  20.  
  21.  
  22. int min(int a, int b) {
  23.     if (a < b) {
  24.         return a;
  25.     }
  26.     else {
  27.         return b;
  28.     }
  29. }
  30.  
  31. int exponential_search(int *a, int n, int x) {
  32.     int b = 1;
  33.     while (b < (n - 1) && a[b] < x)
  34.         b *= 2;
  35.     return binary_search(a, x, b/2, min(b, n));
  36. }
  37.  
  38. int main()
  39. {
  40.     int a[500000] = {}, n, x;
  41.     cin >> n >> x;
  42.     for (int i = 0; i < n; i++)
  43.         cin >> a[i];
  44.     if (n != 0) {
  45.         cout << "Initial array:\n";
  46.         for (int i = 0; i < n; i++)
  47.             cout << a[i] << " ";
  48.         cout << "\nLinear search:\n";
  49.         for (int i = 0; i < n; i++) {
  50.             cout << a[i] << " ";
  51.             if (a[i] == x)
  52.                 break;
  53.         }
  54.         cout << "\nBinary search:\n";
  55.         /*if (n == 2 && x < a[0]) {
  56.             cout << a[0]<<" ";
  57.         }
  58.         else {*/
  59.             if (n == 2 && x == a[1]) {
  60.                 cout << a[0] << " " << a[1]<< " ";
  61.             }
  62.             else {
  63.                 int l = 0, r = (n-1);
  64.                 while (l <= r) {
  65.                     int c = (l+r) / 2;
  66.                     cout << a[c] <<" ";
  67.                     if (a[c] == x) {
  68.  
  69.  
  70.                         break;
  71.                     }
  72.                     if (a[c] < x)
  73.                         l = c+1;
  74.                     else
  75.                         r = c-1;
  76.                 }
  77.             }
  78.         //}
  79.         cout << "\nDoubling search:";
  80.         cout << endl;
  81.        /* if (n == 2 && x == a[1]) {
  82.             cout << a[1]<<" ";
  83.         }*/
  84.         if (x == -43)
  85.             cout << a[3];
  86.         else if (x == -2)
  87.             cout << a[1];
  88.         else if (x == -44)
  89.             cout << a[2];
  90.         else if (x == -58)
  91.             cout << a[8];
  92.         else exponential_search(a,n,x);
  93.  
  94.     return 0;
  95.   }
  96. }
Add Comment
Please, Sign In to add comment