z2d20m5

#include <iostream>
#include <ctime>
using namespace std;

int bin_search(int *a, int key, int left, int right)
{
    int mid = left + (right - left) / 2;

    if (left >= right)
        return 0; // -(1 + left);

    if (a[mid] == key)
        return mid + 1; // a[mid];

    else if (a[mid] > key)
        return bin_search(a, key, left, mid);
    else
        return bin_search(a, key, mid + 1, right);
}

int* Merge(int *a1, int n1, int *a2, int n2)
{
    int *a = new int[n1 + n2];
    int i1 = 0, i2 = 0;
    while (i1 < n1 && i2 < n2)
    {
        if (a1[i1] < a2[i2])
        {
            a[i1 + i2] = a1[i1];
            ++i1;
        }
        else
        {
            a[i1 + i2] = a2[i2];
            ++i2;
        }
    }
    for (; i1 < n1; ++i1)
        a[i1 + i2] = a1[i1];
    for (; i2 < n2; ++i2)
        a[i1 + i2] = a2[i2];
    return a;
}

void MergeSort(int *a, int n)
{
    if (n < 2)
        return;
    int n1 = n >> 1, n2 = n - n1;
    int *a1 = new int[n1];
    int *a2 = new int[n2];
    for (int i = 0; i < n1; ++i)
        a1[i] = a[i];
    for (int i = 0; i < n2; ++i)
        a2[i] = a[n1 + i];
    MergeSort(a1, n1);
    MergeSort(a2, n2);
    delete[] a;
    a = Merge(a1, n1, a2, n2);
    delete[] a1;
    delete[] a2;
}

int main(int argc, const char * argv[]) {
    srand(time(0));
    int n, k;
    cout << "n: ";
    cin >> n;
    cout << "k: ";
    cin >> k;
    int *arr = new int[n];
    int *brr = new int[k];
    for ( int i = 0; i < n; ++i)
        arr[i] = rand() % 10 + 1;
    MergeSort(arr, n);
    cout << "arr: ";
    for ( int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl << "fill in brr: ";
    for ( int i = 0; i < k; ++i)
        cin >> brr[i];
    MergeSort(brr, k);
    for (int i = 0; i < k; ++i) {
        cout << bin_search(arr, brr[i], 0, n) << endl;
    }
    return 0;
}