Advertisement
Guest User

Untitled

a guest
Apr 26th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8. int n;
  9. cin >> n;
  10. vector<int> a;
  11. for (int i = 0; i < n; i++)
  12. {
  13. int s;
  14. cin >> s;
  15. a.push_back(s);
  16. }
  17. sort(a.begin(), a.end());
  18. //сортированный массив
  19. int q; // количество запросов
  20. cin >> q;
  21. for (int i = 0; i < q; i++)
  22. {
  23. int k;
  24. cin >> k;
  25. int l = -1, r = a.size();
  26. bool tr = false;
  27. while (l + 1 < r) // Сам бинарный поиск
  28. {
  29. // l - левая граница которая, r - правая граница и они за массивом изначально
  30. int m = (l + r) / 2;
  31. if (a[m] == k) // Давайте брать m середину и если a[m] то есть m элемент равен k то мы нашли элемент
  32. {
  33. cout << "Yes" << endl;
  34. tr = true;
  35. break;
  36. }
  37. if (a[m] < k) // Если же a[m] != k то если k и есть в нашем массиве то только в интервале (m, r)
  38. l = m;
  39. else // Если же a[m] > k то если k и есть в нашем массиве то только в интервале (l, m)
  40. r = m;
  41. // Мы свели наш интервал к меньшему в два раза
  42. }
  43. if (!tr) // Если мы не нашли элемент
  44. cout << "No" << endl;
  45. }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement