Advertisement
Guest User

Untitled

a guest
Oct 17th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <math.h>
  3.  
  4. void get_limits(const int* A, int size, int value, int* left, int* right) {
  5.     int i = 0;
  6.     while ((int)pow(2, i) < size && A[(int)pow(2, i)] < value) {
  7.         i++;
  8.     }
  9.  
  10.     if (i == 0) {
  11.         *left = 0;
  12.     } else {
  13.         *left = (int)pow(2, i-1);
  14.     }
  15.  
  16.     if (pow(2, i) >= size) {
  17.         *right = size;
  18.     } else {
  19.         *right = (int)pow(2, i);
  20.     }
  21. }
  22.  
  23. int binary_search(const int* A, int value, int left, int right) {
  24.     int first = left;
  25.     int last = right;
  26.     while (first < last) {
  27.         int mid = (first + last) / 2;
  28.         if (A[mid] < value) {
  29.             first = mid + 1;
  30.         } else {
  31.             last = mid;
  32.         }
  33.     }
  34.     return value <= A[last] ? last : right;
  35. }
  36.  
  37. int main() {
  38.     int n = 0, m = 0;
  39.     std::cin >> n >> m;
  40.  
  41.     int* A = (int*) malloc(n * sizeof(int));
  42.     int* B = (int*) malloc(m * sizeof(int));
  43.     for (int i = 0; i < n; i++) {
  44.         std::cin >> A[i];
  45.     }
  46.     for (int i = 0; i < m; i++) {
  47.         std::cin >> B[i];
  48.     }
  49.  
  50.     int left = 0, right = 0;
  51.     for (int i = 0; i < m; i++) {
  52.         get_limits(A, n, B[i], &left, &right);
  53.         std::cout << binary_search(A, B[i], left, right);
  54.         (i != m - 1) ? std::cout << ' ' : std::cout << std::endl;
  55.     }
  56.     free(A);
  57.     free(B);
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement