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

En este artículo, discutiremos la implementación equivalente de Java del método upper_bound() de C++. Este método se proporciona con un valor clave que se busca en la array . Devuelve el índice del primer elemento de la array que tiene un valor mayor que la clave o el último si no se encuentra dicho elemento. Las siguientes implementaciones encontrarán el valor del límite superior y su índice; de ​​lo contrario, imprimirá que el límite superior no existe.

Ilustraciones:

Input  : 10 20 30 30 40 50
Output : upper_bound for element 30 is 40 at index 4

Input  : 10 20 30 40 50
Output : upper_bound for element 45 is 50 at index 4

Input  : 10 20 30 40 50
Output : upper_bound for element 60 does not exists

Ahora analicemos los métodos para usar el método de límite superior() para obtener el índice del siguiente valor mayor.

Métodos:

1. Enfoque ingenuo (búsqueda lineal)
2. Búsqueda binaria iterativa
3. Búsqueda binaria recursiva
4. método binarySearch() de la clase de utilidad Arrays

Analicemos cada uno de los métodos anteriores para una comprensión detallada al proporcionarles programas java limpios de la siguiente manera:

Método 1: usar la búsqueda lineal  

Para encontrar el límite superior mediante la búsqueda lineal, iteramos sobre la array a partir del índice 0 hasta que encontremos un valor mayor que la clave.

Ejemplo

// Java program for finding upper bound
// using linear search
  
// Importing Arrays utility class
import java.util.Arrays;
  
// Main class
class GFG {
  
    // Method 1
    // To find upper bound of given key
    static void upper_bound(int arr[], int key)
    {
        int upperBound = 0;
  
        while (upperBound < arr.length) {
            // If current value is lesser than or equal to
            // key
            if (arr[upperBound] <= key)
                upperBound++;
  
            // This value is just greater than key
            else{
                System.out.print("The upper bound of " + key + " is " + arr[upperBound] + " at index " + upperBound);
                  return;
            }    
        }
        System.out.print("The upper bound of " + key + " does not exist.");
    }
  
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
        // Custom array input over which upper bound is to
        // be operated by passing a key
        int array[] = { 10, 20, 30, 30, 40, 50 };
        int key = 30;
  
        // Sort the array using Arrays.sort() method
        Arrays.sort(array);
  
        // Printing the upper bound
        upper_bound(array, key);
    }
}

The upper bound of 30 is 40 at index 4

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

Espacio Auxiliar: O(1)

Para encontrar el límite superior de una clave, buscaremos la clave en la array. Podemos usar un enfoque eficiente de búsqueda binaria para buscar la clave en la array ordenada en O (log2 n) como se propone en los ejemplos a continuación.  

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

Procedimiento:

1. Ordene la array antes de aplicar la búsqueda binaria.
2. Inicializar bajo como 0 y alto como N.
3. Encuentre el índice del elemento medio (mid)
4. Compara la clave con el elemento central (arr[mid])
5. Si el elemento central es menor o igual a la clave, actualice el valor bajo como medio + 1, de lo contrario, actualice el valor alto como medio.
6. Repita los pasos del 2 al 4 hasta que el nivel bajo sea menor que el nivel alto.
7. Después de todos los pasos anteriores, el mínimo es el límite superior de la clave

Ejemplo

// Java program to Find upper bound
// Using Binary Search Iteratively
  
// Importing Arrays utility class
import java.util.Arrays;
  
// Main class
public class GFG {
  
    // Iterative approach to find upper bound
    // using binary search technique
    static void upper_bound(int arr[], int key)
    {
        int mid, N = arr.length;
  
        // Initialise starting index and
        // ending index
        int low = 0;
        int high = N;
  
        // Till low is less than high
        while (low < high && low != N) {
            // Find the index of the middle element
            mid = low + (high - low) / 2;
  
            // If key is greater than or equal
            // to arr[mid], then find in
            // right subarray
            if (key >= arr[mid]) {
                low = mid + 1;
            }
  
            // If key is less than arr[mid]
            // then find in left subarray
            else {
                high = mid;
            }
        }
  
        // If key is greater than last element which is
        // array[n-1] then upper bound
        // does not exists in the array
        if (low == N ) {
            System.out.print("The upper bound of " + key + " does not exist.");
             return;      
        }
  
          // Print the upper_bound index
          System.out.print("The upper bound of " + key + " is " + arr[low] + " at index " + low);
    }
  
    // Driver main method
    public static void main(String[] args)
    {
        int array[] = { 10, 20, 30, 30, 40, 50 };
        int key = 30;
  
        // Sort the array using Arrays.sort() method
        Arrays.sort(array);
  
        // Printing the upper bound
        upper_bound(array, key);
    }
}

The upper bound of 30 is 40 at index 4

A continuación se analiza un enfoque recursivo que sigue el mismo procedimiento:

Método 3: búsqueda binaria recursiva

Ejemplo

// Java program to Find Upper Bound
// Using Binary Search Recursively
  
// Importing Arrays utility class
import java.util.Arrays;
  
// Main class
public class GFG {
  
    // Recursive approach to find upper bound
    // using binary search technique
    static int recursive_upper_bound(int arr[], int low,
                                     int high, int key)
    {
        // Base Case
        if (low > high || low == arr.length)
            return low;
  
        // Find the value of middle index
        int mid = low + (high - low) / 2;
  
        // If key is greater than or equal
        // to array[mid], then find in
        // right subarray
        if (key >= arr[mid]) {
            return recursive_upper_bound(arr, mid + 1, high,
                                         key);
        }
  
        // If key is less than array[mid],
        // then find in left subarray
        return recursive_upper_bound(arr, low, mid - 1,
                                     key);
    }
  
    // Method to find upper bound
    static void upper_bound(int arr[], int key)
    {
        // Initialize starting index and
        // ending index
        int low = 0;
        int high = arr.length;
  
        // Call recursive upper bound method
        int upperBound
            = recursive_upper_bound(arr, low, high, key);
        if (upperBound == arr.length) 
            // upper bound of the key does not exists
            System.out.print("The upper bound of " + key
                             + " does not exist.");
        else System.out.print(
                "The upper bound of " + key + " is "
                + arr[upperBound] + " at index "
                + upperBound);
    }
  
    // Main driver method
    public static void main(String[] args)
    {
  
        int array[] = { 10, 20, 30, 30, 40, 50 };
        int key = 30;
  
        // Sorting the array using Arrays.sort() method
        Arrays.sort(array);
  
        // Printing the upper bound
        upper_bound(array, key);
    }
}

The upper bound of 30 is 40 at index 4

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

También podemos usar el método de búsqueda binaria incorporado de la clase de utilidad Arrays (o la clase de utilidad Collections). Esta función devuelve un índice de la clave en la array. Si la clave está presente en la array, devolverá su índice (no se garantiza que sea el primer índice); de lo contrario, según el orden ordenado, devolverá la posición esperada de la clave, es decir (-(punto de inserción) – 1). 

Acercarse:

1. Ordene la array antes de aplicar la búsqueda binaria.
2. Busque el índice de la clave en una array ordenada, si está presente en la array, su índice se devuelve como un valor positivo de, de lo contrario, un valor negativo que especifica la posición en la que se debe agregar la clave en la array ordenada.
3. Ahora, si la clave está presente en la array, nos movemos hacia la derecha para encontrar el siguiente valor mayor.
4. Imprima el índice de límite superior si está presente.

Ejemplo

// Java program to find upper bound
// Using binarySearch() method of Arrays class
  
// Importing Arrays utility class
import java.util.Arrays;
  
// Main class
public class GFG {
  
    // Method 1
    // To find upper bound using binary search
    // implementation of Arrays utility class
    static void upper_bound(int arr[], int key)
    {
        int index = Arrays.binarySearch(arr, key);
        int n = arr.length;
  
        // 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 upper bound
            int upperBound = Math.abs(index) - 1;
            if (upperBound < n)
                System.out.print("The upper bound of " + key
                                 + " is " + arr[upperBound]
                                 + " at index "
                                 + upperBound);
            else
                System.out.print("The upper bound of " + key
                                 + " does not exists.");
            return;
        }
  
        // If key is present in the array
        // we move rightwards to find next greater value
        else {
  
            // Increment the index until value is equal to
            // key
  
            while (index < n) {
  
                // If current value is same
                if (arr[index] == key)
                    index++;
  
                // Current value is different which means
                // it is the greater than the key
                else {
                    System.out.print(
                        "The upper bound of " + key + " is "
                        + arr[index] + " at index "
                        + index);
                    return;
                }
            }
            System.out.print("The upper bound of " + key
                             + " does not exist.");
        }
    }
  
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
        int array[] = { 10, 20, 30, 30, 40, 50 };
        int key = 30;
  
        // Sort the array before applying binary search
        Arrays.sort(array);
  
        // Printing the lower bound
        upper_bound(array, key);
    }
}

The upper bound of 30 is 40 at index 4

Nota : también podemos encontrar el índice del elemento central a través de cualquiera de ellos.

int mid = (alto + bajo)/ 2;  

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