La búsqueda binaria omnipresente | Serie 1

Todos somos conscientes del algoritmo de búsqueda binaria. La búsqueda binaria es el algoritmo más fácil y difícil para hacerlo bien. Presento algunos problemas interesantes que recopilé sobre la búsqueda binaria. Hubo algunas requests de búsqueda binaria. Le pido que respete el código: «Intento sinceramente resolver el problema y asegurarme de que no haya casos de esquina». Después de leer cada problema, minimice el navegador e intente resolverlo. Declaración del problema: Dada una array ordenada de N elementos distintos. Encuentre una clave en la array utilizando el menor número de comparaciones. (¿Cree que la búsqueda binaria es óptima para buscar una clave en una array ordenada?) Sin mucha teoría, aquí hay un algoritmo de búsqueda binaria típico. 

// Returns location of key, or -1 if not found
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
  
    while( l <= r )
    {
        m = l + (r-l)/2;
  
        if( A[m] == key ) // first comparison
            return m;
  
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
  
    return -1;
}

// Java code to implement the approach
import java.util.*;
  
class GFG {
  
// Returns location of key, or -1 if not found
static int BinarySearch(int A[], int l, int r, int key)
{
    int m;
  
    while( l < r )
    {
        m = l + (r-l)/2;
  
        if( A[m] == key ) // first comparison
            return m;
  
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
  
    return -1;
}
}
  
// This code is contributed by sanjoy_62.

// C# program to implement
// the above approach
using System;
  
class GFG
{
  
// Returns location of key, or -1 if not found
static int BinarySearch(int[] A, int l, int r, int key)
{
    int m;
  
    while( l < r )
    {
        m = l + (r-l)/2;
  
        if( A[m] == key ) // first comparison
            return m;
  
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
  
    return -1;
}
}
  
// This code is contributed by code_hunt.

<script>
// Javascript code to implement the approach
  
  
// Returns location of key, or -1 if not found
function BinarySearch(A, l, r, key) {
  let m;
  
  while (l < r) {
    m = l + (r - l) / 2;
  
    if (A[m] == key) // first comparison
      return m;
  
    if (A[m] < key) // second comparison
      l = m + 1;
    else
      r = m - 1;
  }
  
  return -1;
}
  
// This code is contributed by gfgking
</script>

En teoría, necesitamos comparaciones log N + 1 en el peor de los casos. Si observamos, estamos usando dos comparaciones por iteración, excepto durante la coincidencia final exitosa, si corresponde. En la práctica, la comparación sería una operación costosa, no será solo una comparación de tipos primitivos. Es más económico minimizar comparaciones como la del límite teórico. Consulte la siguiente figura sobre la inicialización de índices en la próxima implementación. La siguiente implementación utiliza un número menor de comparaciones. 

// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
  
    while( r - l > 1 )
    {
        m = l + (r-l)/2;
  
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
  
    if( A[l] == key )
        return l;
    if( A[r] == key )
        return r;
    else
        return -1;
}

En el ciclo while dependemos solo de una comparación. El espacio de búsqueda converge para colocar l y r apuntan a dos elementos consecutivos diferentes. Necesitamos una comparación más para rastrear el estado de búsqueda. Puede ver un ejemplo de caso de prueba http://ideone.com/76bad0 . ( Código C++ 11 ) Declaración del problema:Dada una array de N enteros distintos, encuentre el valor mínimo de la ‘clave’ de entrada. Digamos, A = {-1, 2, 3, 5, 6, 8, 9, 10} y clave = 7, deberíamos devolver 6 como resultado. Podemos usar la implementación optimizada anterior para encontrar el valor mínimo de la clave. Seguimos moviendo el puntero izquierdo hacia la derecha mientras se mantenga el invariante. Finalmente, el puntero izquierdo apunta a un elemento menor o igual que la clave (por definición, valor mínimo). Los siguientes son posibles casos de esquina, —> Si todos los elementos en la array son más pequeños que la clave, el puntero izquierdo se mueve hasta el último elemento. —> Si todos los elementos de la array son mayores que la clave, es una condición de error. —> Si todos los elementos en la array son iguales y <= clave, es la entrada en el peor de los casos para nuestra implementación. Aquí está la implementación, 

// largest value <= key
// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
// Precondition: A[l] <= key <= A[r]
int Floor(int A[], int l, int r, int key)
{
    int m;
  
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
  
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
  
    return A[l];
}
  
// Initial call
int Floor(int A[], int size, int key)
{
    // Add error checking if key < A[0]
    if( key < A[0] )
        return -1;
  
    // Observe boundaries
    return Floor(A, 0, size, key);
}

Puede ver algunos casos de prueba en http://ideone.com/z0Kx4a . Declaración del problema: Dada una array ordenada con posibles elementos duplicados. Encuentre el número de ocurrencias de la ‘clave’ de entrada en el tiempo de registro N. La idea aquí es encontrar la mayoría de las apariciones de clave a la izquierda y a la derecha en la array mediante la búsqueda binaria. Podemos modificar la función de piso para rastrear la ocurrencia más a la derecha y la ocurrencia más a la izquierda. Aquí está la implementación, 

// Input: Indices Range [l ... r)
// Invariant: A[l] <= key and A[r] > key
int GetRightPosition(int A[], int l, int r, int key)
{
    int m;
  
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
  
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
  
    return l;
}
  
// Input: Indices Range (l ... r]
// Invariant: A[r] >= key and A[l] > key
int GetLeftPosition(int A[], int l, int r, int key)
{
    int m;
  
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
  
        if( A[m] >= key )
            r = m;
        else
            l = m;
    }
  
    return r;
}
  
int CountOccurances(int A[], int size, int key)
{
    // Observe boundary conditions
    int left = GetLeftPosition(A, -1, size-1, key);
    int right = GetRightPosition(A, 0, size, key);
  
    // What if the element doesn't exists in the array?
    // The checks helps to trace that element exists
    return (A[left] == key && key == A[right])?
           (right - left + 1) : 0;
}

Código de muestra http://ideone.com/zn6R6a . Declaración del problema:  dada una array ordenada de elementos distintos, y la array se gira en una posición desconocida. Encuentre el elemento mínimo en la array. Podemos ver la representación pictórica de la array de entrada de muestra en la siguiente figura. Hacemos converger el espacio de búsqueda hasta que l y r  apuntan un solo elemento. Si la ubicación intermedia cae en el primer pulso, la condición A[m] < A[r] no se cumple, hacemos converger nuestro espacio de búsqueda a A[m+1 … r]. Si la ubicación central cae en el segundo pulso, se cumple la condición A[m] < A[r], convergemos nuestro espacio de búsqueda a A[1 … m]. En cada iteración verificamos el tamaño del espacio de búsqueda, si es 1, hemos terminado. A continuación se muestra la implementación del algoritmo. ¿Se te ocurre una implementación diferente? 

int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r)
{
    // extreme condition, size zero or size two
    int m;
  
    // Precondition: A[l] > A[r]
    if( A[l] <= A[r] )
        return l;
  
    while( l <= r )
    {
        // Termination condition (l will eventually falls on r, and r always
        // point minimum possible value)
        if( l == r )
            return l;
  
        m = l + (r-l)/2; // 'm' can fall in first pulse,
                        // second pulse or exactly in the middle
  
        if( A[m] < A[r] )
            // min can't be in the range
            // (m < i <= r), we can exclude A[m+1 ... r]
            r = m;
        else
            // min must be in the range (m < i <= r),
            // we must search in A[m+1 ... r]
            l = m+1;
    }
  
    return -1;
}
  
int BinarySearchIndexOfMinimumRotatedArray(int A[], int size)
{
    return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1);
}

Ver ejemplos de casos de prueba http://ideone.com/KbwDrk . Ejercicios: 1. Una función llamada signum(x, y)  se define como,

signum(x, y) = -1 if x < y
             =  0 if x = y
             =  1 if x > y

¿Se encontró con algún conjunto de instrucciones en el que una comparación se comporte como una función signum ? ¿Puede hacer que la primera implementación de la búsqueda binaria sea óptima? 2. Implementar la función techo réplica de la función suelo. 3. Discute con tus amigos: “¿Es óptima la búsqueda binaria (resulta en el menor número de comparaciones)? ¿Por qué no la búsqueda ternaria o la búsqueda por interpolación en una array ordenada? ¿Cuándo prefiere la búsqueda ternaria o de interpolación a la búsqueda binaria? 4. Dibuje una representación de árbol de la búsqueda binaria (créame, le ayuda mucho a comprender muchas de las partes internas de la búsqueda binaria).

Echa un vistazo al curso de autoaprendizaje de DSA

Estén atentos, cubriré algunos problemas más interesantes usando la búsqueda binaria en los próximos artículos. Doy la bienvenida a sus comentarios. – – – por  Venki . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.