Búsqueda lineal.
La búsqueda lineal es muy sencilla y natural, dado que es la forma en que los seres humanos realizamos búsquedas.
La idea es bastante simple: se va recorriendo uno a uno la secuencia de elementos sobre los que se desea realizar la búsqueda (conjunto de datos), y se va comparando cada uno de ellos con el elemento a buscar (clave o llave); si existe coincidencia, entonces la búsqueda ha tenido éxito y se reporta el índice (posición) del elemento dentro del conjunto de datos.
También puede ocurrir que se haya recorrido todo el conjunto de datos y no se haya encontrado coincidencia con la clave, en cuyo caso se reporta dicha situación con una posición (índice) no válida (-1) respecto al conjunto de datos.
La función busquedaLineal de las líneas 8-15 del Ejemplo 6.5, recibe un arreglo de enteros constantes (el modificador const le indica al compilador que el arreglo es de elementos constantes, y previene al programador de alguna modificación accidental o incidental sobre los elementos del arreglo afectado por el modificador, es decir, vuelve al arreglo afectado de sólo lectura: no es posible modificar sus elementos dentro de la función) a (conjunto de datos), un entero x (clave o llave), y un número n que representa la cantidad de datos del conjunto sobre el que se realizará la búsqueda (podría ser todo el conjunto de datos o sólo una parte de él).
La idea es bastante simple: se va recorriendo uno a uno la secuencia de elementos sobre los que se desea realizar la búsqueda (conjunto de datos), y se va comparando cada uno de ellos con el elemento a buscar (clave o llave); si existe coincidencia, entonces la búsqueda ha tenido éxito y se reporta el índice (posición) del elemento dentro del conjunto de datos.
También puede ocurrir que se haya recorrido todo el conjunto de datos y no se haya encontrado coincidencia con la clave, en cuyo caso se reporta dicha situación con una posición (índice) no válida (-1) respecto al conjunto de datos.
La función busquedaLineal de las líneas 8-15 del Ejemplo 6.5, recibe un arreglo de enteros constantes (el modificador const le indica al compilador que el arreglo es de elementos constantes, y previene al programador de alguna modificación accidental o incidental sobre los elementos del arreglo afectado por el modificador, es decir, vuelve al arreglo afectado de sólo lectura: no es posible modificar sus elementos dentro de la función) a (conjunto de datos), un entero x (clave o llave), y un número n que representa la cantidad de datos del conjunto sobre el que se realizará la búsqueda (podría ser todo el conjunto de datos o sólo una parte de él).
El ciclo for de la línea 11 realiza el recorrido sobre el conjunto de datos, mientras que el if de la línea 12 verifica la coincidencia con el elemento clave; en caso de existir, se reporta en la línea 13, pero si el elemento clave no existe, se reporta dicha situación en la línea 14.
Búsqueda binaria.
La búsqueda binaria se fundamenta en un pre requisito sumamente importante: que el conjunto de datos esté ordenado.
La importancia de tal pre requisito es tal que, si no se cumple, no se garantiza el buen funcionamiento de la búsqueda binaria.
La búsqueda binaria capitaliza el hecho de que los datos estén ordenados para ir eliminando en cada iteración a la mitad de los datos, lo cual la hace muy eficiente; sin embargo, el costo a pagar es el previo ordenamiento de los datos.
Para entender mejor el funcionamiento de la búsqueda binaria utilizaré una analogía con la forma de realizar la búsqueda de una persona en un directorio telefónico (si desconoce por completo lo que estoy diciendo, pregúntele a una persona mayor que no sea de la generación de smartphones lo que era un directorio telefónico antigüo).
La importancia de tal pre requisito es tal que, si no se cumple, no se garantiza el buen funcionamiento de la búsqueda binaria.
La búsqueda binaria capitaliza el hecho de que los datos estén ordenados para ir eliminando en cada iteración a la mitad de los datos, lo cual la hace muy eficiente; sin embargo, el costo a pagar es el previo ordenamiento de los datos.
Para entender mejor el funcionamiento de la búsqueda binaria utilizaré una analogía con la forma de realizar la búsqueda de una persona en un directorio telefónico (si desconoce por completo lo que estoy diciendo, pregúntele a una persona mayor que no sea de la generación de smartphones lo que era un directorio telefónico antigüo).
Suponga que se desea buscar en un directorio telefónico el siguiente nombre: Ricardo Ruiz Rodríguez. En México los nombres aparecen registrados en el directorio en base al primer apellido, segundo apellido y nombre(s) de las personas registradas. Supongamos también que se decide abrir el directorio por la mitad (aproximadamente), y que la lista de apellidos que vemos empieza con Murrieta.
¿Hacia qué parte del directorio deberíamos dirigir la búsqueda? Debería ser obvio que hacia la segunda mitad, ya que Ruiz se encuentra alfabéticamente después que Murrieta. Pues bien, ésta es en esencia la idea de la búsqueda binaria.
El Ejemplo 6.5 muestra en las líneas 17-31 la función que implementa el mecanismo de búsqueda binaria.
La función recibe (línea 17) un arreglo de elementos constantes a (conjunto de búsqueda), el elemento a buscar x (clave o llave), y dos números que representan las posiciones de los límites inferior (lim_inf) y superior (lim_sup) del conjunto de búsqueda respectivamente. Estos límites en general coinciden con el índice inferior y superior del arreglo pero no necesariamente tiene que ser así, ya que el conjunto de búsqueda podría ser un subconjunto de todos los elementos.
¿Hacia qué parte del directorio deberíamos dirigir la búsqueda? Debería ser obvio que hacia la segunda mitad, ya que Ruiz se encuentra alfabéticamente después que Murrieta. Pues bien, ésta es en esencia la idea de la búsqueda binaria.
El Ejemplo 6.5 muestra en las líneas 17-31 la función que implementa el mecanismo de búsqueda binaria.
La función recibe (línea 17) un arreglo de elementos constantes a (conjunto de búsqueda), el elemento a buscar x (clave o llave), y dos números que representan las posiciones de los límites inferior (lim_inf) y superior (lim_sup) del conjunto de búsqueda respectivamente. Estos límites en general coinciden con el índice inferior y superior del arreglo pero no necesariamente tiene que ser así, ya que el conjunto de búsqueda podría ser un subconjunto de todos los elementos.
La expresión condicional de la estructura de repetición while de la línea 20, controla la continuidad o no de la búsqueda del elemento x sobre el arreglo a. En cuanto ya no se cumpla dicha expresión, se sabrá que el elemento clave no existe en el conjunto de búsqueda (¿por qué?), y dicha situación se reporta en la línea 30.
La línea 20 es la fórmula del punto medio y calcula el elemento central del conjunto de búsqueda. En analogía al ejemplo del directorio telefónico, esta sería la simulación de abrirlo aproximadamente a la mitad.
La línea 20 es la fórmula del punto medio y calcula el elemento central del conjunto de búsqueda. En analogía al ejemplo del directorio telefónico, esta sería la simulación de abrirlo aproximadamente a la mitad.
La estructura if/else anidada de las líneas 22-27 determina lo siguiente:
- Si la clave se encontró (línea 22), se regresa su posición dentro del conjunto (línea 23).
- Si no se encontró y hay que buscarla en la parte izquierda del conjunto (línea 24), se ajusta el límite superior (línea 25) para re definir un nuevo subconjunto de búsqueda.
- Si la clave no es igual ni menor respecto al elemento actual (a[medio]), por tricotomía de números, no le queda otra (línea 26) más que estar (si existe) en la parte derecha del conjunto de búsqueda, por lo que se ajusta el límite inferior (línea 27) para re definir el nuevo subconjunto de búsqueda.
Finalmente, si no se ha encontrado la clave y los límites del subconjunto de búsqueda son válidos, se repite nuevamente todo el proceso descrito pero sobre un conjunto de búsqueda con menos datos, de hecho la mitad (aproximadamente) de los datos en cada iteración.
Probablemente el lector haya tenido una sensación parecida a un deja vu y haya venido a su mente el concepto de recursividad (si revisó las entradas correspondientes a recursividad). La búsqueda binaria puede ser abordada utilizando un enfoque recursivo y se deja como ejercicio explorar dicha situación.
Probablemente el lector haya tenido una sensación parecida a un deja vu y haya venido a su mente el concepto de recursividad (si revisó las entradas correspondientes a recursividad). La búsqueda binaria puede ser abordada utilizando un enfoque recursivo y se deja como ejercicio explorar dicha situación.
