Algoritmos de Búsqueda

Borsani, Marcela; De Filippis, Noelia; Navarro, Carlos Andrés; Stekar, Fernando

Simón, Javier; López Arriazu, Francisco; Revel Chion, Andrea

Profesorado de Computación, Facultad de Ciencias Exactas y Naturales-UBA

Contacto: [email protected]
Índice

Página 2
Introducción
El surgimiento de la Ciencia de la Computación, y con ella las aplicaciones en áreas no
numéricas, requieren del conocimiento de nuevos conceptos. Hoy, de hecho, un curso
introductorio a la programación, no necesita de los conocimientos de la matemática
clásica, pero sí de las estructuras de datos y las estructuras matemáticas discretas.
Pensamos por todo esto que, un curso con las características que estamos presentando
en este trabajo, no debe solamente entrenar a los estudiantes en las reglas sintácticas de
un lenguaje de programación específico. Es por esta razón que enfocamos el programa
correspondiente a la materia que aquí evaluamos y detallamos, orientándolo hacia la
resolución de problemas, de una manera clara, sistemática y sencilla, mediante el diseño
de algoritmos.

Comenzamos introduciendo al alumno en las estructuras básicas de la programación en

forma paulatina y a través de ejemplos numéricos y no numéricos sencillos, utilizando un
lenguaje algorítmico que resulta menos riguroso en la sintaxis que los lenguajes de
programación, pero sintetizando características comunes a algunos de los lenguajes de
alto nivel conocidos. Consideramos que las técnicas de programación estructurada
utilizadas en ciertos lenguajes, resultan de mayor claridad sobre aquellos lenguajes que
no las emplean, por este motivo resultaron elegidas para este curso.

Los objetivos más generales que se desea que el alumno incorpore son: comprender a un
algoritmo como una descripción de un proceso; entender cómo es la representación de
los distintos tipos de información dentro de la computadora y cómo eso nos permite
manipular y trabajar con diferentes formatos de datos; analizar diferentes algoritmos para
poder comparar costo y eficiencia de los mismos; incorporar la idea de reutilización de
soluciones, así como también la idea de descomponer un problema en subproblemas más
pequeños. Además de todo esto, se desea que el alumno incorpore y comprenda el valor
de la computadora por el hecho de ser programable.

Consideramos que es un tópico altamente movilizador, ya que los alumnos poseen ideas
previas que muchas veces no se relacionan con los problemas de búsqueda planteados
en la unidad didáctica aquí abordada. Al pensar en búsquedas, los estudiantes no
identifican al problema como tal, y caen en concepciones erróneas en las cuales el poder
de la adivinación les resulta una vía accesible para explicar cualquier situación real. De
todas maneras, no dejaremos de lado en nuestro abordaje el hecho de que una búsqueda
efectuada sobre un conjunto de datos ordenados, podría llevarnos a utilizar cierto carácter
predictivo en la obtención del elemento siguiente, una vez determinada la secuencia de
los elementos dados.

Esta unidad está orientada a chicos cuyas edades oscilan entre 15 y 16 años,
mayormente sin experiencia en programación, excepto lo visto durante el año. La cantidad
de alumnos no debería ser excesiva ya que esto dificultaría el trabajo en clase,
especialmente en las tareas más prácticas. Creemos que un curso de entre 20 y 25
alumnos sería ideal.

Página 3
Proponemos en la primera unidad introducir la motivación, fundamento de los algoritmos y
la representación de datos, para luego pasar a enseñar los mecanismos fundamentales
de programación. Ya a partir de esta unidad, se empiezan a aplicar todos estos conceptos
a problemas más concretos. A continuación, presentamos un esquema del programa para
ver la relación de la Unidad con el resto de los contenidos del año:

Unidad Semanas Temas

I 4 ● ¿Qué es la programación?
● Noción de Algoritmo.
● Representación de datos simples.
● Constantes y variables.
● Expresiones aritméticas.
● Representación de un problema.
II 4 Estructuras de Datos Simples y Operadores
● Tipos de datos.
● Operadores Lógicos y Aritméticos.
● Estructuras de datos simples(vectores).
● Operadores para estructuras de datos básicas.
● Listas lineales.
III 7 Estructuras de control
● Decisión.
● Repetición.
IV 4 Ordenamiento
● Ordenación por selección
● Ordenación por inserción
● Ordenación por intercambio
V 6 Búsqueda
● Motivación. Problemas.
● Algoritmos.
● Distintos criterios de búsqueda.
● Búsqueda en secuencias.
VI 7 Subalgoritmos
● Funciones simples.
● Pasaje de parámetros
● Funciones recursivas y relación con iteración.
● Funciones aplicadas a estructuras de datos simples.
● Procedimientos
VII 7 Árboles, Grafos y Matrices
● El Árbol como estructura de datos.
● Grafos. Representación y búsqueda de un elemento.
● Matrices. Representación y búsqueda de un elemento.

Página 4
Población a la que está dirigida:
Alumnos y alumnas del 4to año de la escuela técnica con especialización en
computación, cursando la materia “Programación I” (16 años).

Prerequisitos:
Se considera que los alumnos:
• Cursan concurrentemente una materia práctica de programación, llamada
“Laboratorio I”, en la cual aplican los conocimientos teóricos aprendidos en
esta materia
• Ya manejan las nociones de problema, algoritmo y representación de datos
• Tienen cierta solvencia en la resolución de problemas simples mediante el
desarrollo de algoritmos en pseudocódigo y diagramas de flujo
• Conocen y pueden operar con tipos de datos simples (enteros, booleanos,
cadenas) y complejos (listas, arreglos, árboles)

Página 5
Tópico Generativo: Algoritmos de Búsqueda
Una aguja en un pajar.... ¿Es difícil de encontrar?

El tópico que hemos elegido es central dentro de la materia aquí presentada, ya que, sin
lugar a dudas, las computadoras gastan la mitad de su tiempo en las operaciones de
ordenación y búsqueda. El ordenamiento provee un medio para la organización de la
información, facilitando, de esta manera la recuperación de datos específicos.
Imaginemos lo difícil que sería usar un diccionario, si sus palabras no estuvieran
ordenadas. Debido a la importancia de estas operaciones se han desarrollado una gran
variedad de algoritmos para tratarlas de los cuales veremos algunos.

Es muy interesante para nosotros lograr que los alumnos lleguen a comprender la
importancia de realizar en primer lugar el ordenamiento y luego la búsqueda de los datos,
ya que la elección de un algoritmo debe tener en cuenta el uso eficiente de la memoria
que se tiene disponible, como así también el tiempo de ejecución del mismo. Al aplicar
primero el ordenamiento y luego la búsqueda, se logra optimizar el uso de los recursos
disponibles.

Lo consideramos accesible para los alumnos ya que estamos trabajando sobre un grupo
que está orientado al aprendizaje de la Computación con cierto grado de profundidad y
que ya ha incursionado en temas relevantes como Algoritmos, estructuras de control,
condiciones, estructuras de datos, variables, constantes, expresiones, cadenas de
caracteres, etc. Los estudiantes inscriptos en esta especialidad tienen la intención de
obtener el conocimiento necesario para una futura experiencia laboral.

Esquema Conceptual
A partir del tópico generativo establecido, proponemos establecer a continuación ciertas
conexiones que resultan interesantes y deseables de ser abordadas dentro de nuestra
planificación de la Unidad didáctica elegida.

Sabemos que un algoritmo de búsqueda es aquel que está diseñado para localizar un
elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar
a una persona en una base de datos, o el mejor movimiento en una partida de ajedrez. La
variante más simple del problema es la búsqueda de un número en un vector. Es
importante determinar si los elementos que deseamos buscar se encuentran ordenados o
no, para establecer de esa manera el mecanismo de abordaje para efectuar la búsqueda.

Se presentarán a lo largo de esta unidad en primer lugar aquellos métodos que busquen
el dato secuencialmente, aplicados en los casos en los cuales resulte un impedimento
Página 6
ordenar los elementos dados previamente.

El método que aquí planteamos, consiste en buscar el elemento comparándolo

secuencialmente con cada elemento del vector hasta encontrarlo, o hasta que se llegue al
final. La existencia se puede asegurar cuando el elemento es localizado, pero no es
posible determinar previamente la no existencia del mismo hasta no haber analizado
todos los elementos.

En el caso en que el vector ya se encuentre previamente ordenado, se utiliza la búsqueda

binaria para determinar la existencia de un elemento. Este tipo de algoritmo reduce el
tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número
de iteraciones necesarias. Es altamente recomendado para buscar en vectores de gran
tamaño, y es el que verán nuestros alumnos.

Para implementar este algoritmo se compara el elemento a buscar con un elemento

cualquiera del vector (normalmente el elemento central): si el valor de éste es mayor que
el del elemento buscado se repite el procedimiento en la parte del vector que va desde el
inicio de éste hasta el elemento seleccionado, en caso contrario se toma la parte del
vector que va desde el elemento seleccionado hasta el final. De esta manera obtenemos
intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el
elemento no se encuentra dentro de este último, entonces se deduce que el elemento
buscado no se encuentra en todo el vector.

Presentando en ambas situaciones los datos de entrada y los algoritmos de búsqueda

que permiten resolverlas respectivamente, lograremos explicar las ventajas de aplicar el
algoritmo de búsqueda una vez realizado el ordenamiento de los elementos dados. De
manera similar, aplicar búsquedas sin ordenar previamente los elementos, dan cuenta del
costo que implica la utilización de este tipo de algoritmos. Sin embargo, este tipo de
métodos es útil en algunos casos en los que el ordenamiento previo resulta un
impedimento real.

Deseamos en esta unidad concientizar al alumno que, aplicar el método adecuado,

favorece el tiempo de respuesta en el proceso de búsqueda y permite optimizar el uso de
los recursos disponibles en la computadora.

Red de Ideas:
Página 7
Hilos Conductores de la asignatura

¿Qué es un algoritmo? ¿Para qué sirve? ¿Qué beneficios nos brinda?

¿Cómo se representan los distintos tipos de datos en la computadora?
¿Cómo podemos darnos cuenta que algunos algoritmos son mejores que otros?
¿Con qué estrategias cuento para solucionar un problema?
¿Cómo puedo aprovechar soluciones que ya encontré?
¿Cuál es la importancia de que la computadora sea programable?

Metas de Comprensión de la unidad didáctica

• Valorar la búsqueda como un problema importante y central. Dar cuenta de su

aparición en diferentes e innumerables contextos, incluyendo muchos que en principio
no parecen problemas de búsqueda.
• Analizar cómo un algoritmo puede ser una manera de resolver problemas de
búsqueda. Poder reconocer las situaciones en donde puedan utilizarse alguno de los
distintos algoritmos de búsqueda.

• Seleccionar/elaborar los criterios para determinar el mejor algoritmo. Lograr

comparar costos y eficiencia de los algoritmos.
• Encontrar la relación entre los distintos criterios de orden o clasificación del
espacio de búsqueda y los algoritmos utilizados en cada caso.

Desempeños de Comprensión de la unidad didáctica

Desempeño Exploratorio 1:

• Para introducir el tema de algoritmos de búsqueda se pregunta a los alumnos en

qué situaciones cotidianas se encuentran frente a problemas de búsqueda.
• Se asume que surgirán tanto temas relacionados con la computadora tales como
buscar personas en Facebook, buscar direcciones en mapas, recorridos de
colectivos, así como también buscar la llave de casa, un tornillo en un cajón, la
media correspondiente al par.
• Los alumnos intentarán diferenciar cuáles de estos problemas de búsqueda
pueden ser resueltos mediante la intervención de una computadora, es decir
mediante el uso de un algoritmo y cuáles no, y de esta manera intercalar el tema
de representación de la información. A aquellos datos que puedan ser
representados en la computadora se les podrá aplicar un algoritmo.
• Los alumnos verán también que, eligiendo una representación adecuada del
problema de búsqueda, es factible hallar un algoritmo como estrategia de
resolución del mismo.
• El docente realizará preguntas abiertas en debate sobre si determinados
problemas son considerados o no problemas de búsqueda. Algunos ejemplos de
Página 8
 estas preguntas son: ¿cómo decidir la siguiente jugada en un partido de ajedrez?,
adivinar un objeto en el que está pensando una persona, encontrar una carta en la
baraja española, buscar antepasados en el árbol genealógico familiar y otros.
• El docente indagará con el objeto de ver qué preconcepciones traen los alumnos
acerca de cuestionamientos tales como ¿en qué consiste un problema de
búsqueda?, ¿cómo lo definirían?¿cómo lo representarían?.
• Los alumnos en grupos de cuatro integrantes recibirán un enunciado con un
problema que consiste en buscar una bolita roja con el número 5 en una caja que
contiene 9 bolitas rojas y 6 azules y determinar su posición(colocar 4 bolitas por
fila y obtener la fila y el lugar que ocupa la bolita roja dentro de la fila). El planteo
se realizará en tres situaciones distintas:
1. Bolitas rojas ordenadas, colocadas antes de las azules.
2. Bolitas rojas ordenadas, colocadas después de las azules.
3. Bolitas rojas y azules mezcladas.
• Luego de hallar la solución para cada situación, los estudiantes intentarán
encontrar una representación posible para cada escenario. Para llevar a cabo
esta instancia contarán con una caja con discos rojos y azules numerados y
deberán representar el problema en papel con las ideas previas obtenidas de
las diferentes unidades vistas en la materia.
• El docente elegirá algunas de las representaciones para discutir en forma
común en el pizarrón y los inducirá a encontrar una forma de representación
adecuada.

Nota: Algunos de los problemas mencionados, serán retomados más adelante en la

unidad con la idea de mostrar que hay problemas de búsqueda que no son trivialmente
identificados como tales.

Desempeño Exploratorio 2:

• El docente entrega a los alumnos organizados en grupos una caja con

elementos a ser clasificados. No inducirá ningún criterio en particular, sólo
pedirá que sus estudiantes clasifiquen los elementos de la caja según algún
criterio que se les ocurra.
• Una vez que hayan terminado de clasificar, el profesor les pedirá a cada grupo
que explique porqué lo hicieron de esa manera.
• Luego el docente realizará preguntas orientadas a responder si hay un única
forma válida o si cada una es útil en determinado contexto. Por ejemplo
formulará preguntas del estilo ¿Y si ahora quiero buscar por …(algún criterio
en el que hayan sido clasificados)... qué me conviene?

Desempeño de Investigación Guiada 1:

• El docente presentará una lista no demasiado extensa de números de

teléfonos y nombres.
• Les pedirá a los alumnos que escriban un algoritmo que dado un nombre,
devuelva el número de teléfono correspondiente a dicho nombre. Con los
temas vistos hasta el momento se espera que la solución sea un algoritmo de
Página 9
 búsqueda lineal.
• A continuación preguntará a sus estudiantes cuántos pasos creen que toma el
algoritmo. Esta pregunta tiene por objeto que puedan visualizar cuantas veces
se pasa por el ciclo que recorre los números de teléfono. Luego el docente
seguirá con una serie de preguntas como: ¿Qué pasa si la lista de números es
mucho mayor?, ¿Y si tengo que buscar muchos nombres? ¿qué pasa si el
elemento no está?, ¿si es el primero? ¿y si es el último? ¿hay alguna forma
más eficiente de hacerlo?, cuando buscan en una agenda, ¿buscan así?
• El docente guiará y ayudará con estas y otras preguntas, de acuerdo con el
rumbo que vaya tomando la clase, para que surja la idea de búsqueda binaria
o algo similar. El profesor espera que con la analogía a la agenda lleguen a
una primera aproximación, que es la idea de que ordenando la lista se puede
hacer más rápido. Una vez que logra ese objetivo, deberá trabajar en ver qué
elemento conviene comparar, para intentar siempre descartar la mayor
cantidad de elementos en cada paso. Como en principio el elemento elegido
puede ser mayor o menor, convendrá elegir el del medio para que siempre se
descarte la mitad de la lista.
• Preguntará entonces cuantos pasos creen que tomaría esta nueva solución.
• A continuación explicará el algoritmo de búsqueda binaria y su costo. Además
se explicará cómo comparar los costos de distintos algoritmos.
• Luego de la explicación, se presentarán algoritmos parecidos, pero con ciertas
variantes, para ver si los alumnos pueden utilizar las herramientas brindadas
para llegar al correcto análisis de los mismos.

Desempeño de Investigación Guiada 2:

• El docente presenta el juego 20Q. Se hace una corrida del juego.

• Pregunta a sus alumnos cómo creen que funciona.
• Genera debate sobre cómo funciona y sobre las preguntas que el juego
realiza.
• Explica un posible algoritmo con el cual funciona el juego.
• Toma un caso particular, por ejemplo una corrida del juego para la cual se
elijan animales, realiza la observación acerca de cómo las preguntas van
“clasificando” la posible incógnita en diferentes categorías.
• Utilizando el juego ¿Quién es Quién?, que consiste en un caso simplificado de
la misma idea (sólo que con apenas 24 candidatos y unas 10 clasificaciones
distintas), el profesor intentará que los alumnos representen los que va
sucediendo mientras progresa el juego. El docente los incentivará a que
representen gráficamente cómo se va achicando el conjunto de candidatos a
medida que se van haciendo preguntas.
• También pueden los alumnos hacer una representación tipo diagrama de flujo
para ver qué sucede dependiendo de la respuesta a cada pregunta. El profesor
mostrará que este diagrama coincide con el de la búsqueda binaria. Discutirán
entre todos al respecto.

Página 10
 • Finalmente, el docente hará una observación acerca de que elegir la pregunta
que mejor divide al conjunto de candidatos, es a su vez un problema de
búsqueda. En este caso un problema que en principio parece ser de
adivinación, se puede ver cómo un problema de búsqueda que a su vez
contiene otro subproblema de búsqueda!

Desempeño Final de Síntesis:

• El docente presenta a sus alumnos distintos tipos de problemas(algunos de los

ya planteados en los desempeños exploratorios y otros nuevos) que
contemplan las diferentes tipos de búsqueda secuencial y binaria, con y sin
ordenamiento de los elementos en ambos casos.
• En base a los enunciados propuestos los alumnos deberán identificar y
clasificar los diferentes problemas presentados de acuerdo a las características
detectadas en cada uno. El docente observará cómo facilita a sus alumnos
dicha actividad para que puedan interpretar a los problemas dados como
problemas de búsqueda. Comprobará si han logrado concretar en su
aprendizaje las dos primeras metas de comprensión planteadas en la unidad.
• Luego el docente presentará diferentes algoritmos de búsqueda escritos en
pseudocódigo, de tal manera que elegirá representativamente uno con
búsqueda secuencial, uno binario, con y sin ordenamiento. Cada uno de los
algoritmos vendrá acompañado de un diagrama de flujo sencillo.
• Los alumnos
Analizarán si los algoritmos presentados son o no de búsqueda.
Compararán su costo, tratando de determinar cuál es mejor.
Establecerán relaciones acerca de la representación elegida, discutirán si
es la mejor manera de representarlo o si encuentran alternativas mejores.

• El docente observará cómo facilita a sus alumnos dicha actividad para que
puedan representar a los problemas dados y elegir el de menor costo.
Comprobará si han logrado concretar en su aprendizaje las dos últimas metas
de comprensión planteadas en la unidad.

Valoración Diagnóstica Continua.

Durante el desarrollo de la unidad se presentan diferentes situaciones partir de las cuales
la mirada sobre los desempeños desarrollados por los alumnos recae en diferentes
protagonistas.

En el caso en que se pide ordenar los elementos de la caja serán los propios alumnos,
quienes “evalúen” entre ellos cuál es el “mejor” criterio de ordenamiento, compartirán las
razones por las cuales decidieron ordenar de esa forma.
Al pedirles que vuelvan a ordenar por otro criterio diferente, los alumnos experimentarán
la posibilidad de un cambio en la forma de búsqueda de algún elemento que el docente
Página 11
les pida encontrar(esta idea está reforzada en el desempeño exploratorio uno y en el 2)
Es deseable que los alumnos comprendan que no hay una única solución correcta, ya
que las posibilidades de ordenamiento son muchas, e ir encontrando las variantes es
parte del desempeño de los alumnos que permitirá al docente realizar una valoración
diagnóstica continua por parte del docente.

En el momento de escribir el algoritmo de búsqueda lineal, se realizarán preguntas al

estudiante que lo llevarán a observar la solución planteada y a chequear su correctitud.
(preguntas del estilo: ¿qué les parece que sucede en este ejemplo? ¿hay alguna otra
manera de plantear el algoritmo en base a la misma lista de elementos? Qué tendríamos
que hacer para que se refleje un cambio en el algoritmo? ¿qué representaría dicho
cambio en el algoritmo? Y en los elementos? En este caso, podemos pensar que al
probar el algoritmo el alumno estará autoevaluándose, y será él quien observe su propio
desempeño.

Siempre estará presente la mirada del docente que durante todo el trabajo observará las
respuestas dadas por los alumnos, qué ideas tiene cada alumno con respecto al tema, si
estas ideas pueden o no obstaculizar el entendimiento del tema a presentar y también
proveerá las herramientas para una adecuada retroalimentación.

Tanto al escribir algoritmos en general cómo en el caso de los de búsqueda, el análisis de

los errores interesa, no sólo desde el punto de vista del algoritmo, sino del lenguaje
algebraico (en el caso de un algoritmo matemático) y también del manejo
de los símbolos.
El modelo constructivista propone no ignorar el error sino provocarlo y analizar su
significado. Según esta postura, el error es indicador de los procesos intelectuales
puestos en juego al momento de resolver una situación de aprendizaje o problemática.
Los errores son el resultado de la aplicación correcta de ciertos procedimientos
imperfectos y son totalmente identificables; evidencian el empleo de métodos y
estrategias inventadas.
Por lo general al pensar en búsquedas, los alumnos no logran identificar al problema
como tal, y esto les provoca confusión e incertidumbre. El docente guiará y acompañará
para que sus alumnos logren elucidar la diferencia entre búsqueda en los problemas de la
vida cotidiana y aquellos otros eventos que no lo son.

Bibliografía.

ÁLVAREZ MÉNDEZ. J.M. (2000). “Didáctica, currículo y evaluación. Ensayos sobre

cuestiones didácticas”. Buenos Aires: Mino y Dávila Editores.
PERKINS, D. (1995) “La escuela inteligente”, “Las campanas de alarma” y “La enseñanza
y el aprendizaje: la Teoría Uno y más allá de la Teoría Uno”. En “La escuela inteligente”.
Barcelona: Ed. Gedisa.
STONEWISKE, M. y cols. (1999) “¿Qué es la enseñanza para la comprensión”? En “La
enseñanza para la comprensión”. Buenos Aires: Paidós.
Página 12