Intuición de búsqueda binaria y funciones de predicado

El algoritmo de búsqueda binaria se usa en muchos problemas de codificación y, por lo general, no es muy obvio a primera vista. Sin embargo, ciertamente hay una intuición y condiciones específicas que pueden insinuar el uso de la búsqueda binaria. En este artículo, tratamos de desarrollar una intuición para la búsqueda binaria.

Introducción a la búsqueda binaria

Es un algoritmo eficiente para buscar un elemento en particular, límite inferior o límite superior en una secuencia ordenada. En caso de que este sea su primer encuentro con el algoritmo de búsqueda binaria, puede consultar este artículo antes de continuar: Lógica básica detrás del algoritmo de búsqueda binaria .

¿Qué es una función monótona? 

Es posible que ya conozcas esto como un concepto matemático.

• Son funciones que siguen un orden particular.
• En términos matemáticos, la pendiente de la función siempre es no negativa o no positiva.
• La monotonicidad es un requisito esencial para utilizar la búsqueda binaria. Recuerde que la búsqueda binaria solo se puede aplicar en una array ordenada [función monotónica].

Por ejemplo, una array no creciente de números: 

Función monótona

¿Qué es una función de predicado?

Son funciones que toman entrada y devuelven una sola salida VERDADERO o FALSO.

Por ejemplo, una función que toma un número entero y devuelve verdadero si el número entero es mayor que 0; de lo contrario, devuelve falso;

Pseudocódigo:

bool isPositive (entrada int) {
    if (entrada > 0) 
        devuelve verdadero;
    de lo contrario, 
        devuelve falso;
}

Función de predicado monotónico:

• Una función de predicado monotónico sería algo como lo siguiente:

Funciones de predicado monotónico

• Por otro lado, esta función a continuación es una función de predicado pero no monótona:

no monótono

• Como se puede observar, en una función de predicado monótona, el valor puede cambiar de verdadero a falso o viceversa, como máximo una vez. Se puede visualizar como una array de 0 y 1 y verificar si la array está ordenada en orden no creciente/no decreciente.

¿Cómo se relacionan la búsqueda binaria y las funciones de predicado monotónico?

La tarea es encontrar el primer verdadero en la array dada:

Función de predicado monotónico

Enfoque ingenuo: el enfoque ingenuo atraviesa la array de principio a fin, se rompe a primera vista de VERDADERO y devuelve el índice.
Complejidad de tiempo: O(n)

Enfoque eficiente: sin embargo, el mejor enfoque es aprovechar el hecho de que la array forma una función monótona, lo que implica que se puede aplicar una búsqueda binaria, que es mejor que una búsqueda lineal.
Complejidad de tiempo: O (logn)

Intuición para la búsqueda binaria:

1. Aparece la función monótona, p. una array ordenada.
2. Necesidad de averiguar el valor mínimo/máximo para el cual se cumple/no se cumple una determinada condición.
3. Se puede formar una función de predicado monótono y se requiere un punto de transición.

Ejemplo: problema del chocolate

Declaración del problema: Dada una array arr[] que consta de las alturas de N barras de chocolate, la tarea es encontrar la altura máxima a la que se realiza el corte horizontal a todos los chocolates de modo que la cantidad restante de chocolate sea al menos K .

Ejemplos:

Entrada : K = 7, arr[] = {15, 20, 8, 17}
Salida: 15
Explicación: Si se hace un corte a la altura 8, el total de chocolate eliminado es 28 
y el chocolate desperdiciado es 28 – 7 = 21 unidades. 
Si se hace un corte a la altura 15, el chocolate eliminado es 7 
y no se desperdicia chocolate. 
Por lo tanto, 15 es la respuesta.

Entrada: K = 12 arr[] = {30, 25, 22, 17, 20}
Salida: 21
Explicación: Después de un corte a la altura 18, el chocolate eliminado es 25 
y el desperdicio de chocolate es (25 – 12) = 13 unidades. 
Pero si el corte se hace a la altura 21 entonces se sacan 14 unidades de chocolate 
y el desperdicio es (14 – 12) = 2 que es lo mínimo. por lo tanto 21 es la respuesta

Observaciones clave: Las observaciones clave relacionadas con el problema son

1. La salida final tiene que ser mayor que igual a 0 ya que esa es la altura mínima a la que se puede hacer un corte horizontal.
2. El resultado final también tiene que ser menor o igual al máximo de alturas de todos los chocolates, ya que todos los cortes por encima de esa altura darán el mismo resultado.
3. Ahora hay un límite inferior y superior.
4. Ahora es necesario encontrar el primer punto en el que el corte de chocolate es mayor o igual a K.
5. Obviamente, podríamos usar una búsqueda lineal para esto, pero eso sería una complejidad de tiempo lineal [O (N)].
6. Sin embargo, dado que se puede formar una función de predicado monótono, también podemos usar la búsqueda binaria, que es mucho mejor con la complejidad del tiempo logarítmico [O(logN)].

Enfoque: esto se puede resolver mediante la búsqueda binaria ya que existe la presencia de una función de predicado monótono. Sigue los pasos:

1. Ya estamos obteniendo un indicio de búsqueda binaria por el hecho de que queremos la «altura máxima [valor extremo] para la cual la suma requerida de la cantidad restante de chocolate es al menos K [condición a satisfacer]».
2. Podemos hacer una función de predicado que tome la altura del corte horizontal y devuelva verdadero si el corte de chocolate es mayor o igual a 7 (k = 7 en el primer ejemplo).

Consulte la ilustración que se muestra a continuación para una mejor comprensión.

Ilustración:

Tome el siguiente caso como ejemplo: K = 7, arr[] = {15, 20, 8, 17} . Inicialmente el máximo como 20 y el mínimo como 0 .

1. Máximo = 20, Mínimo = 10: Ahora medio = (20+0)/2 = 10.
   Cortar a una altura de 10 da, ( (15 – 10) + (20 – 10) + (0) + (17 – 10) ) ) = 22
   Ahora 22 >= 7 pero necesitamos encontrar la altura máxima a la que se cumple esta condición. 
   Así que ahora cambie el espacio de búsqueda a [20, 10] tanto 10 como 20 incluidos. (Tenga en cuenta que debemos mantener 10 en el espacio de búsqueda, ya que podría ser el primer verdadero para la función de predicado)
   Actualice el mínimo a 10.
2. Máximo = 20, Mínimo = 10: Ahora medio = (20+10)/2 = 15.
   Cortar a una altura de 15 da, ((15 – 15) + (20 – 15) + (0) + (17 – 15) ) ) = 7
   Ahora 7 >= 7 pero necesitamos encontrar la altura máxima a la que se cumple esta condición. 
   Así que ahora cambie el espacio de búsqueda a [20, 15] tanto 15 como 20 incluidos.
3. Máximo = 20, Mínimo = 15: Ahora nuevo medio = (20+15)/2 = 17.
   Cortar a una altura de 17 da, ( (0) + (20 – 17) + (0) + (17 – 17) ) = 3
   Ahora 3 < 7 para que podamos eliminar 17 y todas las alturas mayores que 17 ya que se garantiza que todas ellas son falsas. (Tenga en cuenta que aquí debemos excluir 17 del espacio de búsqueda, ya que ni siquiera cumple la condición)
   Ahora quedan 2 elementos en el espacio de búsqueda 15 y 16. 
   Entonces podemos romper el ciclo de búsqueda binaria donde usaremos la condición (alto – bajo > 1).
4. Ahora primero verifique si la condición se cumple para 16, si es así, devuelva 16, de lo contrario, devuelva 15.
5. Aquí desde el 16 no cumple la condición. Soreturn 15, que de hecho es la respuesta correcta.

Tabla de función de predicado

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

// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Predicate function
int isValid(int* arr, int N, int K,
            int height)
{
    // Sum of chocolate cut
    int sum = 0;
 
    // Finding the chocolate cut
    // at this height
    for (int i = 0; i < N; i++) {
        if (height < arr[i])
            sum += arr[i] - height;
    }
 
    // Return true if valid cut
    return (sum >= K);
}
 
int maxHeight(int* arr, int N, int K)
{
 
    // High as max height
    int high = *max_element(arr, arr + N);
 
    // Low as min height
    int low = 0;
 
    // Mid element for binary search
    int mid;
 
    // Binary search function
    while (high - low > 1) {
 
        // Update mid
        mid = (high + low) / 2;
 
        // Update high/low
        if (isValid(arr, N, K, mid)) {
            low = mid;
        }
        else {
            high = mid - 1;
        }
    }
 
    // After binary search we get 2 elements
    // high and low which we can manually compare
    if (isValid(arr, N, K, high)) {
        return high;
    }
    else {
        return low;
    }
}
 
// Driver code
int main()
{
    // Defining input
    int arr[4] = { 15, 20, 8, 17 };
    int N = 4;
    int K = 7;
 
    // Calling the function
    cout << maxHeight(arr, N, K);
    return 0;
}

// java program to implement the approach
import java.util.Arrays;
 
class GFG {
 
  // Predicate function
  static boolean isValid(int[] arr, int N, int K,
                         int height) {
    // Sum of chocolate cut
    int sum = 0;
 
    // Finding the chocolate cut
    // at this height
    for (int i = 0; i < N; i++) {
      if (height < arr[i])
        sum += arr[i] - height;
    }
 
    // Return true if valid cut
    return (sum >= K);
  }
 
  static int maxHeight(int[] arr, int N, int K) {
 
    // High as max height
    int[] a = arr.clone();
    Arrays.sort(a);
    int high = a[a.length - 1];
 
    // Low as min height
    int low = 0;
 
    // Mid element for binary search
    int mid;
 
    // Binary search function
    while (high - low > 1) {
 
      // Update mid
      mid = (high + low) / 2;
 
      // Update high/low
      if (isValid(arr, N, K, mid)) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
 
    // After binary search we get 2 elements
    // high and low which we can manually compare
    if (isValid(arr, N, K, high)) {
      return high;
    } else {
      return low;
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Defining input
    int arr[] = { 15, 20, 8, 17 };
    int N = 4;
    int K = 7;
 
    // Calling the function
    System.out.println(maxHeight(arr, N, K));
  }
}
 
// This code is contributed by saurabh_jaiswal.

# Python code for the above approach
 
# Predicate function
def isValid(arr, N, K, height):
    # Sum of chocolate cut
    sum = 0
 
    # Finding the chocolate cut
    # at this height
    for i in range(N):
        if (height < arr[i]):
            sum += arr[i] - height
 
    # Return true if valid cut
    return (sum >= K)
 
 
def maxHeight(arr, N, K):
 
    # High as max height
    high = max(arr)
 
    # Low as min height
    low = 0
 
    # Mid element for binary search
    mid = None
 
    # Binary search function
    while (high - low > 1):
 
        # Update mid
        mid = (high + low) // 2
 
        # Update high/low
        if (isValid(arr, N, K, mid)):
            low = mid
        else:
            high = mid - 1
 
    # After binary search we get 2 elements
    # high and low which we can manually compare
    if (isValid(arr, N, K, high)):
        return high
    else:
        return low
 
# Driver code
 
 
# Defining input
arr = [15, 20, 8, 17]
N = 4
K = 7
 
# Calling the function
print(maxHeight(arr, N, K))
 
# This code is contributed by Saurabh Jaiswal

// C# program to implement the approach
using System;
 
public class GFG {
 
  // Predicate function
  static bool isValid(int[] arr, int N, int K,
                      int height) {
    // Sum of chocolate cut
    int sum = 0;
 
    // Finding the chocolate cut
    // at this height
    for (int i = 0; i < N; i++) {
      if (height < arr[i])
        sum += arr[i] - height;
    }
 
    // Return true if valid cut
    return (sum >= K);
  }
 
  static int maxHeight(int[] arr, int N, int K) {
 
    // High as max height
    int[] a = new int[arr.Length];
    a =arr;
    Array.Sort(a);
    int high = a[a.Length - 1];
 
    // Low as min height
    int low = 0;
 
    // Mid element for binary search
    int mid;
 
    // Binary search function
    while (high - low > 1) {
 
      // Update mid
      mid = (high + low) / 2;
 
      // Update high/low
      if (isValid(arr, N, K, mid)) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
 
    // After binary search we get 2 elements
    // high and low which we can manually compare
    if (isValid(arr, N, K, high)) {
      return high;
    } else {
      return low;
    }
  }
 
  // Driver code
  public static void Main(String[] args)
  {
 
    // Defining input
    int []arr = { 15, 20, 8, 17 };
    int N = 4;
    int K = 7;
 
    // Calling the function
    Console.WriteLine(maxHeight(arr, N, K));
  }
}
 
// This code is contributed by shikhasingrajput

<script>
       // JavaScript code for the above approach
 
       // Predicate function
       function isValid(arr, N, K,
           height) {
           // Sum of chocolate cut
           let sum = 0;
 
           // Finding the chocolate cut
           // at this height
           for (let i = 0; i < N; i++) {
               if (height < arr[i])
                   sum += arr[i] - height;
           }
 
           // Return true if valid cut
           return (sum >= K);
       }
       function maxHeight(arr, N, K) {
 
           // High as max height
           let high = Math.max(...arr);
 
           // Low as min height
           let low = 0;
 
           // Mid element for binary search
           let mid;
 
           // Binary search function
           while (high - low > 1) {
 
               // Update mid
               mid = Math.floor((high + low) / 2);
 
               // Update high/low
               if (isValid(arr, N, K, mid)) {
                   low = mid;
               }
               else {
                   high = mid - 1;
               }
           }
 
           // After binary search we get 2 elements
           // high and low which we can manually compare
           if (isValid(arr, N, K, high)) {
               return high;
           }
           else {
               return low;
           }
       }
 
       // Driver code
 
       // Defining input
       let arr = [15, 20, 8, 17]
       let N = 4;
       let K = 7;
 
       // Calling the function
       document.write(maxHeight(arr, N, K));
 
      // This code is contributed by Potta Lokesh
   </script>

15

Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)