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.
El código es realmente corto sin los comentarios:
Problemas para practicar
Problemas para practicar
- Considere un arreglo
A[0,N)
de números enteros, conN >= 0
. Se dice queA
tiene un punto fijo si y sólo si existe uni
, con0 <= i < N
, tal queA[i] = i
. Diseñe un algoritmo que dado un arregloA[0,N)
ordenado ascendentemente, calcule en tiempoO(log2 N)
siA
tiene un punto fijo. - Suponga que
A[0,N)
, conN >= 1
, es un arreglo de enteros está ordenado ascendentemente y quex
es un elemento deA
:- Suponiendo que
A
no tiene elementos repetidos, diseñe un algoritmo que en tiempoO(log2 N)
determine cuántos elementos enA
son mayores quex
. - Suponiendo que
A
no tiene elementos repetidos, diseñe un algoritmo que en tiempoO(log2 N)
determine cuántos elementos enA
son mayores o iguales quex
. - Sin suponer que
A
no tiene elementos repetidos, diseñe un algoritmo que en tiempoO(log2 N)
determine cuántos elementos enA
son mayores quex
. - Sin suponer que
A
no tiene elementos repetidos, diseñe un algoritmo que en tiempoO(log2 N)
determine cuántos elementos enA
son mayores o iguales quex
.
- Suponiendo que
- Lo mismo que (2), pero sin suponer que
x
está enA
.