Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. 133
  2. #include <iostream>
  3. #include <math.h>
  4. #include <string>
  5. using namespace std;
  6. int bsearch(int x[100000], int n, int k)
  7. {
  8.     int g1, g2, gm;
  9.     g1 = 0;
  10.     g2 = n - 1;
  11.     gm = (g1 + g2) / 2;
  12.     while (g2 - g1 != 1)
  13.     {
  14.         if (k >= x[gm]) g1 = gm;
  15.         else g2 = gm;
  16.         gm = (g1 + g2) / 2;
  17.     }
  18.     if (x[g2] == k) return g2 + 1;
  19.     if (x[g1] == k) return g1 + 1;
  20.     return -1;
  21. }
  22.  
  23. int main()
  24. {
  25.     freopen("input.txt", "r", stdin);
  26.     freopen("output.txt", "w", stdout);
  27.     int x[100000];
  28.     int n, i, k, m,z1,z2;
  29.     cin >> n;
  30.     for (i = 0;i < n;i++)
  31.         cin >> x[i];
  32.     cin >> m;
  33.     for (i = 0;i < m;i++)
  34.     {
  35.         cin >> k;
  36.         z1 = bsearch(x, n, k);
  37.         z2 = z1;
  38.         if (z1 == -1)
  39.             cout << "Not found" << endl;
  40.         else
  41.         {
  42.             while (x[z2 - 1] == x[z2 - 2])
  43.                 z2--;
  44.             cout << z1-z2+1 << endl;
  45.         }
  46.     }
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement