Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- void get_limits(const int* A, int size, int value, int* left, int* right) {
- int i = 0;
- while ((int)pow(2, i) < size && A[(int)pow(2, i)] < value) {
- i++;
- }
- if (i == 0) {
- *left = 0;
- } else {
- *left = (int)pow(2, i-1);
- }
- if (pow(2, i) >= size) {
- *right = size;
- } else {
- *right = (int)pow(2, i);
- }
- }
- int binary_search(const int* A, int value, int left, int right) {
- int first = left;
- int last = right;
- while (first < last) {
- int mid = (first + last) / 2;
- if (A[mid] < value) {
- first = mid + 1;
- } else {
- last = mid;
- }
- }
- return value <= A[last] ? last : right;
- }
- int main() {
- int n = 0, m = 0;
- std::cin >> n >> m;
- int* A = (int*) malloc(n * sizeof(int));
- int* B = (int*) malloc(m * sizeof(int));
- for (int i = 0; i < n; i++) {
- std::cin >> A[i];
- }
- for (int i = 0; i < m; i++) {
- std::cin >> B[i];
- }
- int left = 0, right = 0;
- for (int i = 0; i < m; i++) {
- get_limits(A, n, B[i], &left, &right);
- std::cout << binary_search(A, B[i], left, right);
- (i != m - 1) ? std::cout << ' ' : std::cout << std::endl;
- }
- free(A);
- free(B);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement