josiftepe

Untitled

Oct 17th, 2020
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <sstream>
  7. #include <cstdio>
  8. #include <algorithm>
  9. #include <stack>
  10. #include <queue>
  11. #include <cmath>
  12. #include <iomanip>
  13. #include <fstream>
  14. //#include <bits/stdc++.h>
  15. using namespace std;
  16. typedef long long ll;
  17. const ll INF = (1 << 30);
  18. const ll inf = (1LL << 60LL);
  19. const int  maxn = 1e5 + 5;
  20.  
  21. int main(int argc, const char * argv[]) {
  22.     ios_base::sync_with_stdio(false);
  23.     // given an array of n elements, check if the number x exists in this array
  24.     // O(log2(n)) time
  25.     int n, x;
  26.     cin >> n >> x;
  27.     vector<int> v(n);
  28.     for(int i = 0; i < n; ++i) {
  29.         cin >> v[i];
  30.     }
  31.     sort(v.begin(), v.end());
  32.     int left_bound = 0;
  33.     int right_bound = n - 1;
  34.     while(left_bound <= right_bound) {
  35.         int middle = (left_bound + right_bound) / 2; // middle of boundaries
  36.         if(v[middle] > x) {
  37.             right_bound = middle - 1;
  38.         }
  39.         else if(v[middle] < x) {
  40.             left_bound = middle + 1;
  41.         }
  42.         else if(v[middle] == x) {
  43.             cout << x << " exists in this array\n";
  44.             break;
  45.         }
  46.        
  47.     }
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment