Búsqueda binaria o dicotómica

Uno de los casos más clásicos de búsquedas y que es todo un clásico justamente porque es muy eficiente y su campo de aplicación es muy muy grande es la búsqueda binaria. Sin embargo, es un poco (sólo un poco) más complejo que una búsqueda lineal. Además esta búsqueda resolverá un caso ligeramente distinto a los otros dos algoritmos vistos.

Idea de la búsqueda

La idea del funcionamiento se basa en datos lexicográficamente ordenados. Supongamos un caso en el que los datos se ingresan de forma creciente. Al tener datos ordenados de esta forma, podemos asegurar dos cosas.

Todos los datos del conjunto se encuentran en un intervalo de tamaños conocido. Donde el primer elemento (el menor) es el límite inferior (todos los demás datos serán mayores o iguales a él) y el último elemento (el mayor) es el límite superior del intervalo (todos los demás datos serán menores o iguales a él).

En base a lo anterior, podemos saber, que si por ejemplo, nuestro límite inferior es \(2\) y nuestro intervalo superior es \(21\), no encontraremos en nuestro conjunto un valor que no encaje en este intervalo. Por ejemplo, el \(-3\) no se encontrará, pues es menor que nuestro límite inferior, tampoco se encontrará el \(50\) pues es un valor más grande que nuestro límite superior. Sin embargo, no podemos conocer a primera vista si el número \(x\) donde \(2 \lt x \lt 21\) se encuentra en el conjunto. Pero esto no significa mayor problema, pues utilizando el mismo razonamiento anterior, podemos responder a la pregunta.

Generamos un ejemplo para el caso en el que se pregunta por el número \(x\) donde \(lim_{inf} \le x \le lim_{sup}\), por ejemplo, con el conjunto de datos \(-2, 0, 1, 3, 4, 7, 10, 25\) tenemos \(lim_{inf} = -2\) y \(lim_{sup} = 25\), además se pregunta por la existencia del número \(x = 15\) en el conjunto. El número \(x\) cae dentro de nuestro intervalo, por lo que no podemos responder inmediatamente, habrá que hacer algo más interesante.

Aplicando el mismo concepto de los intervalos, podemos comenzar con la parte binaria de la búsqueda utilizando el siguiente razonamiento:

Implementación

Para una forma iterativa:

Para una forma recursiva:

Es importante notar que estamos utilizando como límites de cada intervalo los índices del arreglo y no los valores de cada locación, sin embargo, utilizamos los valores para comparar con el valor buscado. Esto tiene sentido, pues los índices nos dicen de dónde a dónde estamos buscando, mientras que los valores nos dicen el límite exacto de cada intervalo. Además, puedes notar que es binaria o dicotómica porque dividimos cada búsqueda en dos partes y en base a un criterio (rangos y límites) seleccionamos una mitad y seguimos buscando. En base a este concepto, no tendrás problema imaginando e implementando una búsqueda terciaria, por ejemplo. Considera también, en los ejemplos anteriores se espera que los datos estén en orden creciente, sin embargo, para el orden decreciente es prácticamente lo mismo, seguro que ya sabes qué partes hay que modificar.

Eficiencia

La búsqueda binaria es sumamente eficiente, en el peor de los casos, para \(N\) datos, el algoritmo tendrá una complejidad \(O(log N)\) lo cual es excelente, el logaritmo es una de las mejores complejidades que podemos encontrar en algoritmos. Sin embargo, es necesario que los datos estén ordenados, o que nos sea posible ordenarlos. En el último caso, debemos considerar también la complejidad de nuestro algoritmo de ordenamiento.

Conclusión

Identifica los mismos aspectos que se señalan en todas las búsquedas, existen distintos estados en la búsqueda (los intervalos que estamos revisando) y realizamos podas (descartamos uno de los intervalos) en base a criterios de selección o condiciones de validez (el valor medio comparado al valor buscado). Al final regresamos el resultado de nuestra búsqueda, ya sea que encontremos el valor o no. Considera que la búsqueda binaria se utiliza no sólo para encontrar valores en un arreglo, sino también para aproximar soluciones de una ecuación, por ejemplo.

Toma en cuenta que la búsqueda binaria es un ejemplo de algoritmo Divide y Vencerás, pues fragmentamos el problema en problemas más pequeños, cuya solución de cada parte nos ayuda a construir la solución final. Más adelante se aborda específicamente este tema. Lo más importante de este algoritmo es el simple y eficiente razonamiento que utiliza, ese principio es muy muy útil y por lo tanto debes tenerlo muy en cuenta al resolver un problema.

¿Notas lo genial y parecidas que son las implementaciones recursivas e iterativas en estos ejemplos? Si aún no comprendes del todo la forma en la que la recursión funciona, compara estos métodos recursivos e iterativos, sus semejanzas y diferencias.

Cita esta página

Include Poetry - Code. (2020, 4 de enero). Búsqueda binaria o dicotómica. Obtenido de https://www.include-poetry.com/Code/C++/Metodos/Busquedas/Binaria/

/* Comentarios */