Primeros pasos en programación con Python

Implementando la búsqueda binaria en Python

A partir del documento anterior podemos ver que la búsqueda binaria representa una manera más rápida de buscar cuando ya tenemos los datos ordenados en nuestros lenguajes de programación…

Se comparte a continuación un ejemplo de la implementación de la busqueda binaria en Python, (disponible en https://trinket.io/library/trinkets/e4092eb2ca):

Recordando en pseudocódigo como funciona el algoritmo la búsqueda binaria, se incluyen pasos para su realización.

Las entradas son el arreglo (lista), el cual llamamos unaLista; el número n de elementos en unaLista lo obtenemos de calcular la longitud de la lista con el metodo len(); y elemento, el número que estamos buscando. La salida es el índice de elemento en unaLista:

  1. Sea primero = 0 y ultimo = n-1.
  2. Calcula puntoMedio como el promedio de ultimo y primero, redondeado hacia abajo (para que sea un entero).
  3. Si unaLista[puntoMedio] es igual a elemento, entonces detente. ¡Lo encontraste! Regresa puntoMedio.
  4. Si el intento fue demasiado alto, es decir, unaLista[puntoMedio] > elemento, entonces haz ultimo = puntoMedio – 1.
  5. De lo contrario, el intento fue demasiado bajo, es decir, unaLista[puntoMedio] < elemento, entonces haz primero = puntoMedio + 1.
  6. Regresa al paso 2.

Para una mejor comprensión les comparto una liga a un material publicado por un académico de la Universidad del Sur de Georgia (http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html), donde se ingresa un valor entre el 1 y el 20 y podemos ver cómo paso a paso se realizar el proceso especificado.

Otro material opcional y adicional para revisar y comprender mejor se encuentra disponible en Khan Academy:

https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/implementing-binary-search-of-an-array

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *