La búsqueda lineal y la búsqueda binaria son algoritmos comunes utilizados para encontrar elementos dentro de una lista. Entendiendo el número esperado de comparaciones que cada algoritmo hace puede ayudar en la elección del método más eficiente para situaciones específicas. Este artículo compara las comparaciones esperadas en métodos de búsqueda lineales versus binarios.

Búsqueda lineal

La búsqueda lineal verifica cada elemento de la lista secuencialmente hasta que encuentre el objetivo o llegue al final. El número esperado de comparaciones depende de si el objetivo está presente y su posición en la lista.

Si la lista contiene n elementos y el objetivo es igualmente probable que esté en cualquier posición, el número esperado de comparaciones es:

Comparaciones revisadas = (n + 1) / 2]

Esto se debe a que, en promedio, la búsqueda encontrará el objetivo a mitad de camino a través de la lista.

Búsqueda binaria

La búsqueda binaria funciona en listas clasificadas dividiendo repetidamente el intervalo de búsqueda en la mitad. Su eficiencia depende del tamaño de la lista y la posición del objetivo.

En el mejor caso, el objetivo está en el medio, requiriendo sólo una comparación. En el peor de los casos, se necesita aproximadamente log2 n] comparaciones.

Asumiendo que el objetivo sea igualmente probable que esté en cualquier posición, el número de comparaciones esperado es aproximadamente:

Comparaciones revisadas ♥ log2 n

Resumen de comparación

  • La búsqueda lineal tiene un recuento de comparación esperado de (n + 1) / 2.
  • La búsqueda binaria tiene un recuento de comparación esperado de aproximadamente log2 n.
  • La búsqueda binaria generalmente requiere menos comparaciones para listas grandes.
  • La búsqueda lineal puede ser preferible para listas pequeñas o sin surtido.