Piso de cada elemento en la misma array

Dada una array de enteros, encuentre el elemento más pequeño o el mismo más cercano para cada elemento. Si todos los elementos son mayores para un elemento, imprima -1. Podemos suponer que la array tiene al menos dos elementos.
Ejemplos: 
 

Entrada: arr[] = {10, 5, 11, 10, 20, 12} 
Salida: 10 -1 10 10 12 11 
Tenga en cuenta que hay múltiples ocurrencias de 10, por lo que el piso de 10 es 10 en sí mismo.
Entrada: arr[] = {6, 11, 7, 8, 20, 12} 
Salida: -1 8 6 7 12 11 
 

Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento seleccionado, recorremos la array restante y encontramos el elemento mayor más cercano. La complejidad temporal de esta solución es O(n*n)
Una mejor solución es ordenar la array y crear una copia ordenada, luego realizar una búsqueda binaria del piso. Recorremos la array, para cada elemento buscamos la primera aparición de un elemento que sea mayor o igual que el elemento dado. Una vez que encontramos dicho elemento, verificamos si el siguiente también es el mismo, si es así, entonces hay múltiples ocurrencias del elemento, por lo que imprimimos el mismo elemento como salida. De lo contrario, imprimimos el elemento anterior en la array ordenada. En C++, límite_inferior()devuelve el iterador al primer elemento mayor o igual en una array ordenada.
 

// C++ implementation of efficient algorithm to find
// floor of every element
#include <bits/stdc++.h>
using namespace std;
 
// Prints greater elements on left side of every element
void printPrevGreater(int arr[], int n)
{
    // Create a sorted copy of arr[]
    vector<int> v(arr, arr + n);
    sort(v.begin(), v.end());
 
    // Traverse through arr[] and do binary search for
    // every element.
    for (int i = 0; i < n; i++) {
 
        // Floor of first element is -1 if there is only
        // one occurrence of it.
        if (arr[i] == v[0]) {
            (arr[i] == v[1]) ? cout << arr[i] : cout << -1;
            cout << " ";
            continue;
        }
 
        // Find the first element that is greater than or
        // or equal to given element
        auto it = lower_bound(v.begin(), v.end(), arr[i]);
 
        // If next element is also same, then there
        // are multiple occurrences, so print it
        if (it != v.end() && *(it + 1) == arr[i])
            cout << arr[i] << " ";
 
        // Otherwise print previous element
        else
            cout << *(it - 1) << " ";
    }
}
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = { 6, 11, 7, 8, 20, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printPrevGreater(arr, n);
    return 0;
}

# Python3 implementation of efficient
# algorithm to find floor of every element
 
# Prints greater elements on left
# side of every element
def printPrevGreater(arr, n) :
 
    # Create a sorted copy of arr
    v = arr.copy()
    v.sort()
     
 
    # Traverse through arr[] and do
    # binary search for every element.
    for i in range(n) :
 
        # Floor of first element is -1 if
        # there is only one occurrence of it.
        if (arr[i] == v[0]) :
            if (arr[i] == v[1]) :
                print(arr[i], end = " ")
                 
            else :
                print(-1, end = " ")
                 
            continue
 
        # Find the first element that is greater
        # than or or equal to given element
        if v.count(arr[i]) > 0:
            it = v[v.index(arr[i])]
        else :
            it = v[n - 1]
             
        # If next element is also same, then there
        # are multiple occurrences, so print it
        if (it != v[n - 1] and
                  v[v.index(it) + 1] == arr[i]) :
            print(arr[i], end = " ")
 
        # Otherwise print previous element
        else :
            print(v[v.index(it) - 1], end = " ")
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 6, 11, 7, 8, 20, 12 ]
    n = len(arr)
    printPrevGreater(arr, n)
 
# This code is contributed by Ryuga

<script>
 
// JavaScript implementation of efficient algorithm to find
// floor of every element
 
// Prints greater elements on left side of every element
function printPrevGreater(arr, n)
{
    // Create a sorted copy of arr[]
    let v = [...arr]
    v.sort((a, b) => a - b);
 
    // Traverse through arr[] and do binary search for
    // every element.
    for (let i = 0; i < n; i++) {
 
        // Floor of first element is -1 if there is only
        // one occurrence of it.
        if (arr[i] == v[0]) {
            (arr[i] == v[1]) ?
            document.write(arr[i]) : document.write(-1);
            document.write(" ");
            continue;
        }
 
        // Find the first element that is greater than or
        // or equal to given element
        if (v.includes(arr[i]))
            it = v[v.indexOf(arr[i])]
        else
            it = v[n - 1]
 
        // If next element is also same, then there
        // are multiple occurrences, so print it
        if (it != v[n - 1] && (v[v.indexOf(it) + 1] == arr[i]))
            document.write(arr[i] + " ");
 
        // Otherwise print previous element
        else
            document.write(v[v.indexOf(it) - 1] + " ");
    }
}
 
function lower_bound(arr, val){
 
     
}
 
/* Driver program to test insertion sort */
 
    let arr = [ 6, 11, 7, 8, 20, 12 ];
    let n = arr.length;
    printPrevGreater(arr, n);
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

-1 8 6 7 12 11

Complejidad de Tiempo : O(n Log n) 
Espacio Auxiliar : O(n)