Búsqueda Binaria | Binary Search
Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/4-binary_search
La búsqueda binaria, también conocida como búsqueda de intervalo medio o búsqueda logarítmica, es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado. Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre. https://es.wikipedia.org/wiki/B%C3%BAsqueda_binaria
Para entender el potencial de este algoritmo debemos entender primero en qué consiste la búsqueda lineal; para esto, pensemos en una lista ordenada de números, en esta lista debemos ubicar la posición de un número específico; la manera más básica de lograrlo es recorrer uno por uno de los elementos comparándolo con el número a buscar hasta encontrarlo, si esto fuera una función, retornaríamos el índice como resultado.
El problema con este método es que la cantidad promedio de elementos que debemos recorrer para encontrar cualquier elemento aumenta con la longitud de la lista, por ejemplo: si hablamos de una lista de 5 elementos, encontrar el elemento en la mitad de la lista nos tomaría 3 pasos; Si esta lista fuera de 50 elementos, nos tomaría 25 pasos y si esta tuviera 500 elementos, nos tomaría 250.
Para reducir la cantidad de pasos necesaria, la búsqueda binaria propone dividir la lista en mitades y seleccionar solo la mitad en la que podría encontrarse el elemento que buscamos, una vez que descartamos el resto de elementos realizamos el mismo procedimiento con el bloque que conservamos; de esta manera, si tuviéramos 100 elementos, encontrar el elemento de la posición 52 nos tomaría:
Esto mismo, de la manera lineal nos hubiera tomado 52 pasos del 1 → 100 o 48 pasos del 100 → 1.
Ejemplo:
Vamos a jugar adivinanzas, tomaremos un texto aleatorio y trataremos de adivinar caracter por caracter de manera lineal y luego utilizando búsqueda binaria.
Para ello necesitamos obtener el texto de algún lado y luego contar con una función a la que le podamos dar la posición y un carater, y esta nos indique si el caracter enviado coincide con la posición o si es mayor/menor a este.
El texto lo obtendremos de http://www.randomtext.me/ utilizando su API.
