quick - Implementación de C lower_bound

search binary java

Question

Basado en la siguiente definición encontrada here

Devuelve un iterador que apunta al primer elemento del rango ordenado [primero, último) que no compara menos que el valor. La comparación se realiza utilizando el operador <para la primera versión, o comp para la segunda.

¿Cuál sería la implementación equivalente de C de lower_bound ()? Entiendo que sería una modificación de la búsqueda binaria, pero parece que no puede identificar la implementación exacta.

int lower_bound(int a[], int lowIndex, int upperIndex, int e);

Caso de muestra:

int a[]= {2,2, 2, 7 };

lower_bound(a, 0, 1,2) would return 0 --> upperIndex is one beyond the last inclusive index as is the case with C++ signature.

lower_bound(a, 0, 2,1) would return 0.

lower_bound(a, 0, 3,6) would return 3;
lower_bound(a, 0, 4,6) would return 3; 

Mi intento de código se da a continuación:

int low_bound(int low, int high, int e)
{
    if ( low < 0) return 0;
    if (low>=high )
    {
      if ( e <= a[low] ) return low;
      return low+1;
    }
    int mid=(low+high)/2;
    if ( e> a[mid])
        return low_bound(mid+1,high,e);
    return low_bound(low,mid,e);

}

Answer 1

Aquí están las implementaciones equivalentes de upper_bound y lower_bound . Este algoritmo es O (log (n)) en el peor de los casos, a diferencia de la respuesta aceptada que llega a O (n) en el peor de los casos.

Tenga en cuenta que aquí high índice high se establece en n lugar de n - 1 . Estas funciones pueden devolver un índice que está más allá de los límites de la matriz. Es decir, devolverá el tamaño de la matriz si no se encuentra la clave de búsqueda y es mayor que todos los elementos de la matriz.

int bs_upper_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid = (l + h) / 2;
        if (x >= a[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

int bs_lower_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid = (l + h) / 2;
        if (x <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

La implementación real de C ++ funciona para todos los contenedores. Puedes encontrarlo here .

Answer 2

Implementación de C ++

int lower_bound(vector<int>& array, int target) {
    int lo = 0, hi = (int)array.size() - 1;
    int mid;

    while(lo < hi) {
        mid = lo + ((hi - lo) >> 1);
        /* low <= mid < high */
        if (array[mid] < target)
            lo = mid + 1;
        else
            hi = mid;
    }

    return lo;
}

Answer 3

Las funciones lower_bound y upper_bound en python se implementarían de la siguiente manera:

def binLowerBound(a, lo, hi, x):
  if (lo > hi):
    return hi
  mid = (lo + hi) / 2;
  if (a[mid] == x):
    return binLowerBound(a, lo, mid-1, x)
  elif (a[mid] > x):
    return binLowerBound(a, lo, mid-1, x)
  else:
    return binLowerBound(a, mid+1, hi, x)

def binHigherBound(a, lo, hi, x):
  if (lo > hi):
    return lo
  mid = (lo + hi) / 2;
  if (a[mid] == x):
    return binHigherBound(a, mid+1, hi, x)
  elif (a[mid] > x):
    return binHigherBound(a, lo, mid-1, x)
  else:
    return binHigherBound(a, mid+1, hi, x)

Answer 4

Sé que este es un post muy antiguo. Sin embargo, estaba trabajando en un problema y encontré esta publicación. Me gustaría agregar mi versión iterativa para el problema que es una extensión de la última respuesta. Revisé esto con los casos de prueba que pude pensar. He adjuntado mi código en C #.

Este código estaba funcionando para todos los rangos. Sin embargo, el rango debe estar dentro del primer índice hasta el último índice + 1. Si la matriz es de tamaño N y considera el rango como [0, N], el espacio de búsqueda estará dentro de [0, N). Sé que eso es bastante obvio, pero me ayudó a revisar algunos casos de borde.

        static int lower_bound(int[] a, int lo,int hi, int x)
        {
            while (lo < hi) 
            {
                int mid = lo + (hi-lo) / 2;
                if(a[mid]==x)
                {
                    /*when there is a match, we should keep on searching
                    for the next same element. If the same element is not                                                         
                    found, mid is considered as the answer and added to ''hi''
                    Finally ''hi'' is returned*/
                    if(a[mid-1]!=x)
                    {
                        hi=mid;
                        break;
                    }
                    else
                        hi=mid-1; 
                }
                else if(a[mid]>x)
                    hi=mid-1;
                else
                    lo=mid+1;
            }
            //if element is not found, -1 will be returned   
            if(a[hi]!=x)
                return -1;
            return hi;
        }
        static int upper_bound(int[] a, int lo,int hi, int x)
        {
            int temp=hi;
            while (lo < hi) 
            {
                int mid = lo + (hi-lo) / 2;
                if(a[mid]==x)
                {
                    /*this section make sure that program runs within        
                    range [start,end)*/
                    if(mid+1==hi)
                    {   
                        lo=mid;
                        break;
                    }
                    /*when there is a match, we should keep on searching
                      for the next same element. If the same element is not                                                         
                      found, mid is considered as the answer and added to
                      ''lo''. Finally ''lo'' is returned*/ 
                    if(a[mid+1]!=x)
                    {
                        lo=mid;
                        break;
                    }
                    else
                        lo=mid+1;
                }


         else if(a[mid]>x)
             hi=mid-1;
         else
             lo=mid+1;
    }
    //if element is not found, -1 will be returned
    if(a[lo]!=x)
            return -1;
        return lo;
    }

Aquí hay un caso de prueba que utilicé:

Array(a) : 1 2 2 2 2 5 5 5 5
size of the array(a) : 9

Considerando el elemento de búsqueda como 2:

upper_bound(a,0,9,2)=4, lower_bound(a,0,9,2)=1

Considerando el elemento de búsqueda como 5:

upper_bound(a,0,9,2)=8, lower_bound(a,0,9,2)=5

Considerando el elemento de búsqueda como 1:

upper_bound(a,0,9,2)=0, lower_bound(a,0,9,2)=0

Considerando el elemento de búsqueda como 5:

upper_bound(a,5,9,2)=8, lower_bound(a,5,9,2)=5

Answer 5

lower_bound es casi como hacer una búsqueda binaria habitual, excepto:

1. Si no se encuentra el elemento, devuelve su lugar actual en la búsqueda, en lugar de devolver un valor nulo.
2. Si se encuentra el elemento, busque hacia la izquierda hasta que encuentre un elemento no coincidente. Luego devuelve un puntero / iterador al primer elemento coincidente.

Sí, es realmente tan simple. :-)

Answer 6

int lowerBound (int *a, int size, int val) {
   int lo = 0, hi = size - 1;
   while (lo < hi) {
      int mid = lo + (hi - lo)/2;
      if (a[mid] < val)
         lo = mid + 1;
      else
         hi = mid;
   }
   return lo;
}