Búsqueda binaria frente a búsqueda lineal
La búsqueda lineal, también conocida como búsqueda secuencial, es el algoritmo de búsqueda más simple. Busca un valor específico en una lista comprobando cada elemento de la lista. La búsqueda binaria también es un método utilizado para localizar un valor específico en una lista ordenada. El método de búsqueda binaria reduce a la mitad el número de elementos comprobados (en cada iteración), lo que reduce el tiempo necesario para localizar el elemento dado en la lista.
¿Qué es la búsqueda lineal?
La búsqueda lineal es el método de búsqueda más simple, que verifica cada elemento en una lista secuencialmente hasta que encuentra un elemento específico. La entrada al método de búsqueda lineal es una secuencia (como una matriz, una colección o una cadena) y el elemento que debe buscarse. El resultado es verdadero si el elemento especificado está dentro de la secuencia proporcionada o falso si no está en la secuencia. Dado que este método verifica todos los elementos de la lista hasta que se encuentra el elemento especificado, en el peor de los casos, revisará todos los elementos de la lista antes de encontrar el elemento requerido. La complejidad de la búsqueda lineal es o(n). Por lo tanto, se considera que es demasiado lento para buscar elementos en listas grandes. Pero esto es muy simple y fácil de implementar.
¿Qué es la búsqueda binaria?
La búsqueda binaria también es un método utilizado para ubicar un elemento específico en una lista ordenada. Este método comienza comparando el elemento buscado con los elementos en el medio de la lista. Si la comparación determina que los dos elementos son iguales, el método se detiene y devuelve la posición del elemento. Si el elemento buscado es mayor que el elemento del medio, vuelve a iniciar el método utilizando solo la mitad inferior de la lista ordenada. Si el elemento buscado es menor que el elemento del medio, vuelve a iniciar el método utilizando solo la mitad superior de la lista ordenada. Si el elemento buscado no está dentro de la lista, el método devolverá un valor único que lo indica. Por tanto, el método de búsqueda binaria reduce a la mitad el número de elementos comparados (en cada iteración), dependiendo del resultado de la comparación. En consecuencia, la búsqueda binaria se ejecuta en tiempo logarítmico, lo que da como resultado un rendimiento de caso promedio de o(log n).
¿Cuál es la diferencia entre la búsqueda binaria y la búsqueda lineal?
Aunque tanto la búsqueda lineal como la búsqueda binaria son métodos de búsqueda, tienen varias diferencias. Mientras que la búsqueda binaria opera en listas ordenadas, la búsqueda lineal también puede operar en listas no ordenadas. Ordenar una lista generalmente tiene una complejidad de caso promedio de n log n. la búsqueda lineal es simple y directa de implementar que la búsqueda binaria. Sin embargo, la búsqueda lineal es demasiado lenta para usarse con listas grandes debido a su rendimiento promedio de casos. Por otro lado, la búsqueda binaria se considera un método más eficiente que podría usarse con listas grandes. Pero implementar la búsqueda binaria podría ser bastante complicado y un estudio ha demostrado que el código exacto para la búsqueda binaria se puede encontrar en solo cinco de veinte libros.
