Equivalente en Java del método lower_bound() de C++

El método lower_bound() de C++ devuelve el índice del primer elemento de la array que tiene un valor no menor que la clave. Esto significa que la función devuelve el índice del siguiente número más pequeño justo mayor o igual que ese número. Si hay varios valores que son iguales al número, lower_bound() devuelve el índice del primero de esos valores.

Ejemplos:  

Entrada: 4 6 10 12 18 18 20 20 30 45
Salida: límite inferior para el elemento 18 en el índice 4

Entrada: 4 6 10 12 16 20 28
Salida: límite inferior para el elemento 18 en el índice 5

Entrada: 24 26 40 56
Salida: límite inferior para el elemento 18 en el índice 0

Entrada: 4 6 10 12 16 17
Salida: límite inferior para el elemento 18 en el índice 6

Ahora discutamos los métodos para usar el método lower_bound() para obtener el índice del siguiente número más pequeño justo mayor o igual a ese número.

Métodos:

1. Enfoque ingenuo
2. Usando la búsqueda binaria iterativamente
3. Usando la búsqueda binaria recursivamente
4. Usando el método binarySearch() de la clase de utilidad Arrays

Método 1: usar la búsqueda lineal 
Podemos usar la búsqueda lineal para encontrar lower_bound . Iteramos sobre la array a partir del índice 0 hasta que encontremos un valor igual o mayor que la clave.

A continuación se muestra la implementación del enfoque anterior:

// Java program for finding lower bound
// using linear search
 
// Importing Arrays utility class
import java.util.Arrays;
 
// Main class
class GFG {
 
    // Method 1
    // To find lower bound of given key
    static int lower(int array[], int key)
    {
        int lowerBound = 0;
 
        // Traversing the array using length function
        while (lowerBound < array.length) {
 
            // If key is lesser than current value
            if (key > array[lowerBound])
                lowerBound++;
 
            // This is either the first occurrence of key
            // or value just greater than key
            else
                return lowerBound;
        }
 
        return lowerBound;
    }
 
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
        // Custom array input over which lower bound is to
        // be operated by passing a key
        int array[]
            = { 4, 6, 10, 12, 18, 18, 20, 20, 30, 45 };
        int key = 18;
 
        // Sort the array using Arrays.sort() method
        Arrays.sort(array);
 
        // Printing the lower bound
        System.out.println(lower(array, key));
    }
}

4

Complejidad temporal: O(N), donde N es el número de elementos de la array.
Espacio Auxiliar: O(1)

Podemos usar un enfoque eficiente de búsqueda binaria para buscar la clave en la array ordenada en O (log ₂ n) como se propone en el siguiente ejemplo 

Método 2: usar la búsqueda binaria de forma iterativa

Procedimiento:

1. Inicialice el bajo como 0 y el alto como N.
2. Compara la clave con el elemento central (arr[mid])
3. Si el elemento medio es mayor o igual que la clave, actualice el alto como un índice medio (medio).
4. De lo contrario, actualice bajo como medio + 1.
5. Repita los pasos del 2 al 4 hasta que el nivel bajo sea menor que el nivel alto.
6. Después de todos los pasos anteriores, el mínimo es el límite inferior de una clave en la array dada.

A continuación se muestra la implementación del enfoque anterior:

// Java program to Find lower bound
// Using Binary Search Iteratively
 
// Importing Arrays utility class
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Method 1
    // Iterative approach to find lower bound
    // using binary search technique
    static int lower_bound(int array[], int key)
    {
        // Initialize starting index and
        // ending index
        int low = 0, high = array.length;
        int mid;
 
        // Till high does not crosses low
        while (low < high) {
 
            // Find the index of the middle element
            mid = low + (high - low) / 2;
 
            // If key is less than or equal
            // to array[mid], then find in
            // left subarray
            if (key <= array[mid]) {
                high = mid;
            }
 
            // If key is greater than array[mid],
            // then find in right subarray
            else {
 
                low = mid + 1;
            }
        }
 
        // If key is greater than last element which is
        // array[n-1] then lower bound
        // does not exists in the array
        if (low < array.length && array[low] < key) {
            low++;
        }
 
        // Returning the lower_bound index
        return low;
    }
 
    // Method 2
    // Driver main method
    public static void main(String[] args)
    {
 
        // Custom array and key input over which lower bound
        // is computed
        int array[]
            = { 4, 6, 10, 12, 18, 18, 20, 20, 30, 45 };
        int key = 18;
 
        // Sort the array  using Arrays.sort() method
        Arrays.sort(array);
 
        // Printing the lower bound
        System.out.println(lower_bound(array, key));
    }
}

4

Complejidad temporal: O(logN)
Espacio auxiliar: O(1)

Ahora, como de costumbre, optimizando más lejos al proporcionar un enfoque recursivo siguiendo el mismo procedimiento que se discutió anteriormente.

Método 3: usar la búsqueda binaria recursivamente

// Java program to Find Lower Bound
// Using Binary Search Recursively
 
// Importing Arrays utility class
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Method 1
    // To find lower bound using binary search technique
    static int recursive_lower_bound(int array[], int low,
                                     int high, int key)
    {
        // Base Case
        if (low > high) {
            return low;
        }
 
        // Find the middle index
        int mid = low + (high - low) / 2;
 
        // If key is lesser than or equal to
        // array[mid] , then search
        // in left subarray
        if (key <= array[mid]) {
 
            return recursive_lower_bound(array, low,
                                         mid - 1, key);
        }
 
        // If key is greater than array[mid],
        // then find in right subarray
        return recursive_lower_bound(array, mid + 1, high,
                                     key);
    }
 
    // Method 2
    // To compute the lower bound
    static int lower_bound(int array[], int key)
    {
        // Initialize starting index and
        // ending index
        int low = 0, high = array.length;
 
        // Call recursive lower bound method
        return recursive_lower_bound(array, low, high, key);
    }
 
    // Method 3
    // Main driver method
    public static void main(String[] args)
    {
        // Custom array and key over which lower bound is to
        // be computed
        int array[]
            = { 4, 6, 10, 12, 18, 18, 20, 20, 30, 45 };
        int key = 18;
 
        // Sorting the array using Arrays.sort() method
        Arrays.sort(array);
 
        // Printing the lower bound
        System.out.println(lower_bound(array, key));
    }
}

4

Complejidad de Tiempo: O(logN)
Espacio Auxiliar: O(logN)

Método 4: Usar el método binarySearch() de la clase de utilidad Arrays

También podemos usar la implementación de búsqueda binaria incorporada de la clase de utilidad Arrays (o la clase de utilidad Collections). La función devuelve un índice de la clave de búsqueda, si está contenida en la array; de lo contrario, (-(punto de inserción) – 1). El punto de inserción se define como el punto en el que se insertaría la clave en la array. 

Acercarse:

1. Ordenar la array antes de aplicar la búsqueda binaria
2. Busque el índice de la clave en la array ordenada usando Arrays.binarysearch()
   • Verifique si la clave está presente en la array, si es verdadera, devuelva el índice de la clave como un valor positivo.
   • De lo contrario, un valor negativo que especifica la posición en la que se debe agregar la clave a la array ordenada.
3. Si la clave está presente en la array, nos movemos hacia la izquierda para encontrar su primera aparición.
4. de lo contrario, habríamos obtenido un valor negativo de un índice, usándolo para calcular el valor del «punto de inserción» (es decir, el índice del primer elemento mayor que la clave)
5. Imprímelo.

A continuación se muestra la implementación del enfoque anterior:

// Java program to find lower bound
// using binarySearch() method of Arrays class
 
// Importing Arrays utility class
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Method 1
    // To find lower bound using binary search
    // implementation of Arrays utility class
    static int lower_bound(int array[], int key)
    {
 
        int index = Arrays.binarySearch(array, key);
 
        // If key is not present in the array
        if (index < 0) {
 
            // Index specify the position of the key
            // when inserted in the sorted array
            // so the element currently present at
            // this position will be the lower bound
            return Math.abs(index) - 1;
        }
 
        // If key is present in the array
        // we move leftwards to find its first occurrence
        else {
 
            // Decrement the index to find the first
            // occurrence of the key
 
            while (index > 0) {
 
                // If previous value is same
                if (array[index - 1] == key)
                    index--;
 
                // Previous value is different which means
                // current index is the first occurrence of
                // the key
                else
                    return index;
            }
 
            return index;
        }
    }
 
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
        //
        int array[]
            = { 4, 6, 10, 12, 18, 18, 20, 20, 30, 45 };
        int key = 18;
 
        // Sort the array before applying binary search
        Arrays.sort(array);
       
        // Printing the lower bound
        System.out.println(lower_bound(array, key));
    }
}

4

Complejidad temporal: O(logN)
Espacio auxiliar: O(1)

Nota: También podemos encontrar el valor medio a través de cualquiera de ellos.

int mid = (alto + bajo)/ 2;  
int mid = (bajo + alto) >>> 1;