Diferencia Entre Búsqueda Binaria Y Búsqueda Lineal

2024 Autor: Mildred Bawerman | [email protected]. Última modificación: 2023-12-16 08:38

Búsqueda binaria vs 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 todos los elementos de la lista. La búsqueda binaria también es un método utilizado para ubicar 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), reduciendo 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, colección o una cadena) y el elemento que se debe buscar. 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, pasará por 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 usarlo cuando se buscan elementos en listas grandes. Pero esto es muy simple y más fácil de implementar.

¿Qué es la búsqueda binaria?

La búsqueda binaria también es un método que se utiliza para localizar 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 intermedio, 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 lo 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. Por consiguiente,La búsqueda binaria se ejecuta en tiempo logarítmico, lo que da como resultado un rendimiento de caso promedio 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 binaria son métodos de búsqueda, tienen varias diferencias. Mientras que la búsqueda binaria opera en listas ordenadas, la búsqueda interna también puede operar en listas no ordenadas. La clasificación de una lista generalmente tiene una complejidad de caso promedio de n log n. La búsqueda lineal es más simple y directa de implementar que la búsqueda binaria. Pero 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 solo se puede encontrar en cinco de veinte libros.