Elemento mayor más cercano para cada elemento de array de otra array

Dadas dos arrays a[] y b[], necesitamos construir una array c[] tal que cada elemento c[i] de c[] contenga un valor de a[] que sea mayor que b[i] y sea el más cercano a b[yo]. Si a[] no tiene un elemento mayor que b[i], entonces el valor de c[i] es -1. Todas las arrays son del mismo tamaño. 

Ejemplos:

Input : a[] = [ 2, 6, 5, 7, 0]  
        b[] = [1, 3, 2, 5, 8]
Output : c[] = [2, 5, 5, 7, -1]

Input : a[] = [ 2, 6, 5, 7, 0]   
        b[] = [0, 2, 3, 5, 1]
Output : c[] = [2, 5, 5, 6, 2]

Enfoque ingenuo: para cada elemento en b[], recorremos todo a[] e intentamos encontrar el elemento mayor más cercano y guardamos el resultado para cada búsqueda. Esto costará una complejidad de tiempo de O (n ^ 2). 

Enfoque eficiente: ordene la array a[] y, para cada b[i], aplique la búsqueda binaria en la array ordenada a[]. Para este método nuestra complejidad de tiempo será O(nlogn).

 Nota: Para el elemento mayor más cercano, podemos usar upper_bound() . 

A continuación se muestra la implementación. 

// CPP to find result from target array
// for closest element
#include <bits/stdc++.h>
using namespace std;
 
// Function for printing resultant array
void closestResult(int a[], int b[], int n)
{
    // change arr[] to vector
    vector<int> vect(a, a + n);
 
    // sort vector for ease
    sort(vect.begin(), vect.end());
 
    // iterator for upper_bound
    vector<int>::iterator up;
 
    // vector for result
    vector<int> c;
 
    // calculate resultant array
    for (int i = 0; i < n; i++) {
 
        // check upper bound element
        up = upper_bound(vect.begin(), vect.end(), b[i]);
 
        // if no element found push -1
        if (up == vect.end())
            c.push_back(-1);
 
        // Else push the element
        else
            c.push_back(*up); // add to resultant
    }
 
    cout << "Result = ";
    for (auto it = c.begin(); it != c.end(); it++)
        cout << *it << " ";
}
 
// driver program
int main()
{
    int a[] = { 2, 5, 6, 1, 8, 9 };
    int b[] = { 2, 1, 0, 5, 4, 9 };
    int n = sizeof(a) / sizeof(a[0]);
    closestResult(a, b, n);
    return 0;
}

// Java to find result from target array
// for closest element
import java.util.*;
 
class GFG
{
 
    // Function for printing resultant array
    static void closestResult(Integer[] a,
                              int[] b, int n)
    {
 
        // change arr[] to Set
        TreeSet<Integer> vect = new TreeSet<>(Arrays.asList(a));
 
        // vector for result
        Vector<Integer> c = new Vector<>();
 
        // calculate resultant array
        for (int i = 0; i < n; i++)
        {
 
            // check upper bound element
            Integer up = vect.higher(b[i]);
 
            // if no element found push -1
            if (up == null)
                c.add(-1);
 
            // Else push the element
            else
                c.add(up); // add to resultant
        }
 
        System.out.print("Result = ");
        for (int i : c)
            System.out.print(i + " ");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        Integer[] a = { 2, 5, 6, 1, 8, 9 };
        int[] b = { 2, 1, 0, 5, 4, 9 };
        int n = a.length;
 
        closestResult(a, b, n);
    }
}
 
// This code is contributed by
// sanjeev2552

# Python implementation to find result
# from target array for closest element
 
import bisect
 
# Function for printing resultant array
def closestResult(a, b, n):
     
    # sort list for ease
    a.sort()
 
    # list for result
    c = []
 
    # calculate resultant array
    for i in range(n):
 
        # check location of upper bound element
        up = bisect.bisect_right(a, b[i])
 
        # if no element found push -1
        if up == n:
            c.append(-1)
         
        # else push the element
        else:
            c.append(a[up]) # add to resultant
     
    print("Result = ", end = "")
    for i in c:
        print(i, end = " ")
 
 
# Driver code
if __name__ == "__main__":
    a = [2,5,6,1,8,9]
    b = [2,1,0,5,4,9]
    n = len(a)
    closestResult(a, b, n)
 
# This code is contributed by
# sanjeev2552

Result = 5 2 1 6 5 -1

Complejidad de Tiempo: O(n log ₂ (n))
Espacio Auxiliar: O(n)