Advertisement
Guest User

Untitled

a guest
Feb 17th, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int bin_search(int x, vector <int> &A) {
  7. int l = 0, r = A.size();
  8. while(l < r - 1){
  9. int mid = (l + r)/2;
  10. if (A[mid] > x)
  11. r = mid;
  12. else
  13. l = mid;
  14. }
  15. if (l == A.size() - 1 || A[r] - x >= x - A[l]) {
  16. while(l > 0 && A[l-1] == A[l]) --l;
  17. return l;
  18. }
  19. return r;
  20. }
  21.  
  22. int main()
  23. {
  24. int n, m;
  25. cin >> n;
  26. vector <int> A(n);
  27. for (int i = 0; i < n; ++i){
  28. cin >> A[i];
  29. }
  30. cin >> m;
  31. for (int i = 0; i < m; ++i){
  32. int x;
  33. cin >> x;
  34. cout << bin_search(x, A) << " ";
  35. }
  36. return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement