Búsqueda binaria

Post date: Mar 20, 2013 1:06:20 AM

A continuación encuentran el algoritmo de búsqueda binaria que estudiamos hoy en clase, con un par de ajustes. Su eficiencia logarítmica en función del tamaño del espacio de búsquda (es decir, corre en tiempo O(log2 N) en donde N es tamaño del espacio de búsqueda) radica en que cada vez que avanza la búsqueda, se descarta una mitad del espacio de búsquda pendiente, hasta que sólo resta un elemento en el espacio de búsqueda. Al final del anuncio encuentran un par de problemas para practicar el concepto de búsqueda binaria.

El código Python está completamente documentado para que puedan estudiar y entender cómo funciona. Además hay un par de pruebas.

Problemas para practicar

1. Considere un arreglo A[0,N) de números enteros, con N >= 0. Se dice que A tiene un punto fijo si y sólo si existe un i, con 0 <= i < N, tal que A[i] = i. Diseñe un algoritmo que dado un arreglo A[0,N) ordenado ascendentemente, calcule en tiempo O(log2 N) si A tiene un punto fijo.
2. Suponga que A[0,N), con N >= 1, es un arreglo de enteros está ordenado ascendentemente y que x es un elemento de A:
   • Suponiendo que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores que x.
   • Suponiendo que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores o iguales que x.
   • Sin suponer que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores que x.
   • Sin suponer que A no tiene elementos repetidos, diseñe un algoritmo que en tiempo O(log2 N) determine cuántos elementos en A son mayores o iguales que x.
3. Lo mismo que (2), pero sin suponer que x está en A.