es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Cómo puedo hacer más eficiente este código de búsqueda binaria?

12 Jul, 2023 Programación

public class MiBusqueda {

public static int buscar(MiArray array, int valor) {

    int indice = -1;

    int inicio = 0, fin = array.length - 1;

    while(inicio <= fin) {

        int medio = (inicio + fin) / 2;

        if(array.compValor(medio, valor) == 1) fin = medio - 1;
        else if(array.compValor(medio, valor) == -1) inicio = medio + 1;
        else return medio;
    }

    return indice;

}

}

En algunos casos, como se puede ver en la captura de pantalla, se excede el número de comparaciones. No se me permite utilizar operaciones de lectura (get). El número de comparaciones que se me permite realizar es O(logn).

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    El problema con la implementación actual es que no es lo suficientemente eficiente para matrices grandes, ya que realiza más comparaciones de las necesarias. Para reducir el número de comparaciones, podemos modificar el algoritmo de búsqueda para utilizar una técnica conocida como búsqueda por interpolación.

    La búsqueda por interpolación es un algoritmo de búsqueda que utiliza el valor que se está buscando, el valor mínimo de la matriz y el valor máximo de la matriz para estimar la posición del valor que se está buscando. El algoritmo utiliza la proporción entre la diferencia entre el valor que se está buscando y el valor mínimo y la diferencia entre el valor máximo y el valor mínimo para estimar la posición del valor que se está buscando. Con la búsqueda por interpolación, podemos realizar menos comparaciones y, por lo tanto, mejorar la eficiencia de nuestro algoritmo de búsqueda.

    Para implementar la búsqueda por interpolación, modificaremos el método de búsqueda en la clase MySearch de la siguiente manera:

    public class MySearch {

    public static int search(MyArray array, int value) {

        int index = -1;

        int start = 0, end = array.length - 1;

        while(start <= end && value >= array[start] && value <= array[end]) {

            int pos = start + (((end - start) /
              (array[end] - array[start])) * (value - array[start]));

            if(array[pos] == value) return pos;

            if(array[pos] < value) start = pos + 1;

            else end = pos - 1;
        }

        return index;
    }
}

    El método de búsqueda modificado utiliza la fórmula de interpolación para estimar la posición del valor que se está buscando. Primero verifica si la posición estimada es el valor que se está buscando, y si no lo es, actualiza las posiciones de inicio y fin en función de si el valor que se está buscando es mayor o menor que la posición estimada.

    Con esta modificación, ahora podemos realizar la operación de búsqueda en complejidad de tiempo O(log log n), siempre que la matriz esté distribuida de manera uniforme.

Comments are closed.