Busqueda lineal y binaria

Solo disponible en BuenasTareas
  • Páginas : 2 (397 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de marzo de 2012
Leer documento completo
Vista previa del texto
BUSQUEDA LINEAL LIMLITADA SEGUN ORDEN RECURSIVA

La recursividad constituye una de las herramientasmas potentes en programacion.
Ventajas: No es necesario definir la secuencia de
pasos exactapara resolver el problema.
Desventajas: Podrıa ser menos eficiente.
Ejemplo: Calculo del factorial con n=3.
3! = 3 * 2!

3! = 3 * 2!

2! = 2 * 1!

3! = 3 * 2!

2! = 2* 1!
1! = 1 * 0!

3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1(caso base)
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 1
1
3! = 3 * 2!
2! = 2 * 11! = 1 * 1 = 1
3! = 3 * 2
2! = 2 * 1 = 2

3! = 3 * 2 = 6

Para resolver un problema
Tendremos que diseñar: casos base, casosgeneralesy la solucion en terminos de ellos.
Casos base: Son los casos del problema que se resuelve con un segmento de código sin recursividad.
Los casos generales siempre deben avanzar hacia un caso base.Es decir, la llamada recursiva se hace a un sub. problemas mas pequeño y, en ultima instancia, los casos generales alcanzaran un caso base.

BUSQUEDA BINARIA ITERATIVA

La búsqueda binariaconsiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro.
Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (siestá) en el primer subarray, y si es mayor está en el segundo.

La búsqueda binaria divide el espacio de búsqueda cada vez a la mitad, comportándose de la siguiente manera: n, n/2, n/4, n/8, n/16...esta serie tiene un comportamiento logarítmico, por lo cual el ciclo en el peor de los casos se realizará cuantas veces sea necesario hacer para encontrar el numero.

Por ejemplo, para buscar...
tracking img