- La búsqueda de un elemento en una secuencia es un algoritmo básico pero importante. El problema que intenta resolver puede plantearse de la siguiente manera: Dada una secuencia de valores y un valor, devolver el índice del valor en la secuencia, si se encuentra, de no encontrarse el valor en la secuencia señalizarlo apropiadamente.
- Una de las formas de resolver el problema es mediante la búsqueda lineal, que consiste en ir revisando uno a uno los elementos de la secuencia y comparándolos con el elemento a buscar. Este algoritmo no requiere que la secuencia se encuentre ordenada.
- Cuando la secuencia sobre la que se quiere buscar está ordenada, se
puede utilizar el algoritmo de búsqueda binaria. Al estar ordenada
la secuencia, se puede desacartar en cada paso la mitad de los
elementos, quedando entonces con una eficiencia algorítmica relativa
al
log(len(secuencia)). Este algoritmo sólo tiene sentido utilizarlo sobre una secuencia ordenada. - El análisis del comportamiento de un algoritmo puede ser muy engañoso si se tiene en cuenta el mejor caso, por eso suele ser mucho más ilustrativo tener en cuenta el peor caso. En algunos casos particulares podrá ser útil tener en cuenta, además, el caso promedio.
Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola,
Maximiliano Curia, Marcos Medrano, Nicolás Paez.
La copia y redistribución de esta página se permite bajo los términos
de la licencia Creative Commons Atribución - Compartir Obras Derivadas
Igual 3.0 siempre que se conserve esta nota de copyright.