algorithm - iterativa - busqueda binaria pseint

Encontrar entradas múltiples con búsqueda binaria.

Question

Utilizo la búsqueda binaria estándar para devolver rápidamente un solo objeto en una lista ordenada (con respecto a una propiedad clasificable).

Ahora necesito modificar la búsqueda para que se devuelvan TODAS las entradas de la lista coincidente. ¿Cómo debo hacer esto mejor?

Answer 1

¿Su búsqueda binaria devuelve el elemento, o el índice al que está el elemento? ¿Se puede obtener el índice?

Dado que la lista está ordenada, todos los elementos coincidentes deben aparecer adyacentes. Si puede obtener el índice del elemento devuelto en la búsqueda estándar, solo tiene que buscar en ambas direcciones desde ese índice hasta que no encuentre coincidencias.

Answer 2

Bueno, como la lista está ordenada, todas las entradas que le interesan son contiguas . Esto significa que necesita encontrar el primer elemento igual al elemento encontrado, mirando hacia atrás desde el índice que fue producido por la búsqueda binaria. Y lo mismo sobre el último artículo.

Simplemente puede retroceder desde el índice encontrado, pero de esta manera la solución puede ser tan lenta como O (n) si hay muchos elementos iguales a los encontrados. Por lo tanto, debería utilizar mejor la búsqueda exponencial : duplique sus saltos a medida que encuentre más elementos iguales. De esta manera, toda su búsqueda sigue siendo O (log n).

Answer 3

Comenzaría por encontrar el índice de un solo elemento dada la propiedad clasificable (usando la búsqueda binaria "normal") y luego comenzar a mirar hacia la izquierda y derecha del elemento en la lista, agregando todos los elementos encontrados para cumplir con la búsqueda criterio, deteniéndose en un extremo cuando un elemento no cumple con el criterio o no hay más elementos para atravesar, y deteniéndose por completo cuando los extremos izquierdo y derecho cumplen las condiciones de detención mencionadas anteriormente.

Answer 4

Esto depende de la implementación de la búsqueda binaria que utilice:

• En Java y .NET, la búsqueda binaria le dará un elemento arbitrario; debe buscar ambas formas para obtener el rango que está buscando.
• En C ++, puede usar el método de equal_range para producir el resultado que desea en una sola llamada.

Para acelerar las búsquedas en Java y .NET para casos en los que el rango igual es demasiado largo para iterar de forma lineal, puede buscar un elemento predecesor y el elemento sucesor, y tomar valores en el centro del rango que encuentre, exclusivo de Los finales.

Si esto es demasiado lento debido a una segunda búsqueda binaria, considere escribir su propia búsqueda que busque ambos extremos al mismo tiempo. Esto puede ser un poco tedioso, pero debería correr más rápido.

Answer 5

Haría dos búsquedas binarias, una buscando el primer elemento comparando> = el valor (en términos de C ++, lower_bound) y luego una buscando el primer elemento comparando> el valor (en términos de C ++, upper_bound). Los elementos desde lower_bound hasta justo antes del límite superior son lo que está buscando (en términos de java.util.SortedSet, subconjunto (clave, clave)).

Por lo tanto, necesita dos modificaciones leves diferentes a la búsqueda binaria estándar: todavía prueba y usa la comparación en la sonda para reducir el área en la que debe estar el valor que está buscando, pero ahora, por ejemplo, lower_bound, si alcanza la igualdad, todo lo que sabemos es que el elemento que está buscando (el primer valor igual) está en algún lugar entre el primer elemento del rango hasta el momento y el valor que acaba de sondear, no puede regresar inmediatamente.

Answer 6

Primero recordemos el fragmento de código de búsqueda binario ingenuo:

int bin_search(int arr[], int key, int low, int high)
{
    if (low > high)
        return -1;

    int mid = low + ((high - low) >> 1);

    if (arr[mid] == key) return mid;
    if (arr[mid] > key)
        return bin_search(arr, key, low, mid - 1);
    else
        return bin_search(arr, key, mid + 1, high);
}

Citado de Prof.Skiena: Supongamos que eliminamos la prueba de igualdad si (s [middle] == key) return (middle); desde la implementación anterior y devuelva el índice bajo en lugar de -1 en cada búsqueda fallida. Todas las búsquedas no tendrán éxito ahora, ya que no hay una prueba de igualdad. La búsqueda procederá a la mitad derecha cuando la clave se compare con un elemento de matriz idéntico, terminando finalmente en el límite derecho. Repetir la búsqueda después de invertir la dirección de la comparación binaria nos llevará al límite izquierdo. Cada búsqueda toma tiempo O (lgn), por lo que podemos contar las ocurrencias en tiempo logarítmico independientemente del tamaño del bloque.

Por lo tanto, necesitamos dos rondas de binary_search para encontrar el lower_bound (encontrar el primer número no menos que la KEY) y el upper_bound (encontrar el primer número más grande que la KEY).

int lower_bound(int arr[], int key, int low, int high)
{
    if (low > high)
        //return -1;
        return low;

    int mid = low + ((high - low) >> 1);
    //if (arr[mid] == key) return mid;

    //Attention here, we go left for lower_bound when meeting equal values
    if (arr[mid] >= key) 
        return lower_bound(arr, key, low, mid - 1);
    else
        return lower_bound(arr, key, mid + 1, high);
}

int upper_bound(int arr[], int key, int low, int high)
{
    if (low > high)
        //return -1;
        return low;

    int mid = low + ((high - low) >> 1);
    //if (arr[mid] == key) return mid;

    //Attention here, we go right for upper_bound when meeting equal values
    if (arr[mid] > key) 
        return upper_bound(arr, key, low, mid - 1);
    else
        return upper_bound(arr, key, mid + 1, high);
}

Espero que sea útil :)

Answer 7

Prueba esto. Funciona asombrosamente.

ejemplo de trabajo, haga clic aquí

   var arr = [1, 1, 2, 3, "a", "a", "a", "b", "c"]; // It should be sorted array.
   // if it arr contain more than one keys than it will return an array indexes. 

   binarySearch(arr, "a", false);

   function binarySearch(array, key, caseInsensitive) {
       var keyArr = [];
       var len = array.length;
       var ub = (len - 1);
       var p = 0;
       var mid = 0;
       var lb = p;

       key = caseInsensitive && key && typeof key == "string" ? key.toLowerCase() : key;

       function isCaseInsensitive(caseInsensitive, element) {
           return caseInsensitive && element && typeof element == "string" ? element.toLowerCase() : element;
       }
       while (lb <= ub) {
           mid = parseInt(lb + (ub - lb) / 2, 10);

           if (key === isCaseInsensitive(caseInsensitive, array[mid])) {
               keyArr.push(mid);
               if (keyArr.length > len) {
                   return keyArr;
               } else if (key == isCaseInsensitive(caseInsensitive, array[mid + 1])) {
                   for (var i = 1; i < len; i++) {
                       if (key != isCaseInsensitive(caseInsensitive, array[mid + i])) {
                           break;
                       } else {
                           keyArr.push(mid + i);

                       }
                   }
               }
               if (keyArr.length > len) {
                   return keyArr;
               } else if (key == isCaseInsensitive(caseInsensitive, array[mid - 1])) {
                   for (var i = 1; i < len; i++) {

                       if (key != isCaseInsensitive(caseInsensitive, array[mid - i])) {
                           break;
                       } else {
                           keyArr.push(mid - i);
                       }
                   }
               }
               return keyArr;

           } else if (key > isCaseInsensitive(caseInsensitive, array[mid])) {
               lb = mid + 1;
           } else {
               ub = mid - 1;
           }
       }

       return -1;
   }

Answer 8

Puede utilizar el siguiente código para su problema. El objetivo principal aquí es primero encontrar el límite inferior de la clave y luego encontrar el límite superior de la misma. Más tarde obtenemos la diferencia de los índices y obtenemos nuestra respuesta. En lugar de tener dos funciones diferentes, podemos usar una bandera que se puede usar para encontrar el límite superior y el límite inferior en la misma función.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int bin_search(int a[], int low, int high, int key, bool flag){
long long int mid,result=-1;
while(low<=high){
    mid = (low+high)/2;
    if(a[mid]<key)
        low = mid + 1;
    else if(a[mid]>key)
        high = mid - 1;
    else{
        result = mid;
        if(flag)
            high=mid-1;//Go on searching towards left (lower indices)
        else
            low=mid+1;//Go on searching towards right (higher indices)
    }
}
return result;
}

int main() {

int n,k,ctr,lowind,highind;
cin>>n>>k;
//k being the required number to find for
int a[n];
for(i=0;i<n;i++){
    cin>>a[i];
}
    sort(a,a+n);
    lowind = bin_search(a,0,n-1,k,true);
    if(lowind==-1)
        ctr=0;
    else{
        highind = bin_search(a,0,n-1,k,false);
        ctr= highind - lowind +1;   
}
cout<<ctr<<endl;
return 0;
}

Answer 9

Si estoy siguiendo tu pregunta, tienes una lista de objetos que, para fines de comparación, se parecen a {1,2,2,3,4,5,5,5,6,7,8,8,9} . Una búsqueda normal de 5 afectará a uno de los objetos que se comparan como 5, pero desea obtenerlos todos, ¿no es así?

En ese caso, sugeriría una búsqueda binaria estándar que, al aterrizar en un elemento coincidente, comience a mirar a la izquierda hasta que deje de coincidir, y luego a la derecha (desde la primera coincidencia) nuevamente hasta que deje de coincidir.

¡Tenga cuidado de que cualquier estructura de datos que esté utilizando no sobrescriba los elementos que se comparan con los mismos!

Alternativamente, considere usar una estructura que almacene elementos que se comparen con el mismo que un cubo en esa posición.

Answer 10

Un algoritmo muy eficiente para esto fue encontrado recientemente.
El algoritmo tiene una complejidad de tiempo logarítmica considerando ambas variables (tamaño de entrada y cantidad de claves buscadas). Sin embargo, las claves buscadas también deben ser ordenadas.

#define MIDDLE(left, right) ((left) + (((right) - (left)) >> 1))

int bs (const int *arr, int left, int right, int key, bool *found)
{
    int middle = MIDDLE(left, right);

    while (left <= right)
    {
        if (key < arr[middle])
            right = middle - 1;
        else if (key == arr[middle]) {
            *found = true;
            return middle;
        }
        else
            left = middle + 1;
        middle = MIDDLE(left, right);
    }

    *found = false;
    /* left points to the position of first bigger element */
    return left;
}

static void _mkbs (const int *arr, int arr_l, int arr_r,
                   const int *keys, int keys_l, int keys_r, int *results)
{
    /* end condition */
    if (keys_r - keys_l < 0)
        return;

    int keys_middle = MIDDLE(keys_l, keys_r);

    /* throw away half of keys, if the key on keys_middle is out */
    if (keys[keys_middle] < arr[arr_l]) {
        _mkbs(arr, arr_l, arr_r, keys, keys_middle + 1, keys_r, results);
        return;
    }
    if (keys[keys_middle] > arr[arr_r]) {
        _mkbs(arr, arr_l, arr_r, keys, keys_l, keys_middle - 1, results);
        return;
    }

    bool found;
    int pos = bs(arr, arr_l, arr_r, keys[keys_middle], &found);

    if (found)
        results[keys_middle] = pos;

    _mkbs(arr, arr_l, pos - 1, keys, keys_l, keys_middle - 1, results);
    _mkbs(arr, (found) ? pos + 1 : pos, arr_r, keys, keys_middle + 1, keys_r, results);
}

void mkbs (const int *arr, int N, const int *keys, int M, int *results)
{   _mkbs(arr, 0, N - 1, keys, 0, M - 1, results);   }

Aquí está la implementación en C y un borrador para la publicación: https://github.com/juliusmilan/multi_value_binary_search

¿Puedes por favor compartir un caso de uso?

Answer 11

Una vez que encontraste una coincidencia con bsearch, solo bsearch recursivo por ambos lados hasta que no haya más coincidencias

pseudo codigo

    range search (type *array) {
      int index = bsearch(array, 0, array.length-1);

      // left
      int upperBound = index -1;
      int i = upperBound;
      do {
         upperBound = i;
         i = bsearch(array, 0, upperBound);
      } while (i != -1)

      // right
      int lowerBound = index + 1;
      int i = lowerBound;
      do {
         lowerBound = i;
         i = bsearch(array, lowerBound, array.length);
      } while (i != -1)

      return range(lowerBound, UpperBound);
}

Sin embargo, no hay casos de esquina cubiertos. Creo que esto mantendrá su complejidad para (O (logN)).

Answer 12

class binary_search_descending_multiple_s
{
    public static void main(int s)
    {
        int a[]={100,100,100,100,100,100,100,100,99,100,87,80,90,78,87,8,64,100,99,99,99,99,99,99};
        int l=a.length;
        int i,x,c,fv=0,lv=l-1,m;
        for(i=0;i<l-1;i++)
        {
            for(x=i+1;x<l;x++)
            {
                if(a[i]<a[x])//descending order used
                {
                 c=a[i];
                 a[i]=a[x];
                 a[x]=c;
                }
            }
        }
        c=0;
        while(fv<=lv&&c==0)
        {
            m=(lv+fv)/2;
            if(a[m]==s)
            {
                System.out.println("found at"+(m+1));
                int xr=m+1;//for right side nos 
                int xl=m-1;//for left side nos
                c=0;
                while(c>=-1 && xr<a.length)
                {
                      if(a[xr]==s)
                      System.out.println("found at"+(xr+1));
                      else//to terminate the loop
                      break;
                      xr++;//increment to check terms further right
                }
                while(c>=0 && xl>=0)//for left side
                {
                     if(a[xl]==s)
                     System.out.println("found at"+(xl+1));
                     else//to terminate the loop
                     break;
                     xl-=1;//decrement to check terms further left
                }
                c=1;
            }
            if(a[m]<=s)
             lv=m-1;
            if(a[m]>s)
             fv=m+1;
        }
    }
}

Este programa ordenará los datos en orden descendente y luego buscará. Funciona con saltos simples, aunque los saltos dobles pueden hacer que pierdas un valor. Lee el programa y lo entenderás.