Algoritmos de Búsqueda
Algoritmo secuencial
# ================== # Programa principal # ================== # Genero un vector con 20 elementos colocados en posiciones aleatorias, de números entre 1 y 100 numeroDeElementos = 20 maximoNumeroAparecido = 100 misNumeros = [] for i in range(1,maximoNumeroAparecido+1): longitud = len(misNumeros) misNumeros.insert(random.randint(0,longitud),i) misNumeros = misNumeros[:20] # solo quiero 20 números print "Mis números: ",misNumeros print "= = = " # =========================================================================== # Búsqueda secuencial # ¿En qué lugar encuentro uno de los números? # Uso búsqueda secuencial cuando la lista no es ordenada o no puedo ordenarla # Método más lento. No queda más remedio que recorrer uno a uno. # Comprobar si tengo el elemento, y si no salir # =========================================================================== numeroAleatorio = misNumeros[random.randint(0,len(misNumeros)-1)] print "El número elegido es el %d" % (numeroAleatorio) indice = 0 while indice<(len(misNumeros)-1): if misNumeros[indice]==numeroAleatorio: print "Lo encuentro en el lugar %d del vector, contando desde 0" % (indice) indice = len(misNumeros)-1 indice+=1
Búsqueda por dicotomía
La búsqueda por dicotomía (o binaria) se caracteriza por dividir el array en dos partes, si es que no encuentra el valor en el índice dado. Y va calculando índices, por divisiones sucesivas. Es mucho más rápido que el anterior.En el siguiente ejemplo se encuentra implementado sin recursividad o con recursividad. Como el array debe estar ordenado, uso el método quicksort visto anteriormente.
# *-* coding: utf-8 *-* import random def quicksort(L, first, last): # definimos los índices y calculamos el pivote i = first j = last pivote = (L[i] + L[j]) / 2 # print "PIVOTE: ",str(pivote) # iteramos hasta que i no sea menor que j while i < j: # iteramos mientras que el valor de L[i] sea menor que pivote while L[i] < pivote: # Incrementamos el índice i+=1 # print "i: ",str(i) # iteramos mientras que el valor de L[j] sea mayor que pivote while L[j] > pivote: # decrementamos el índice j-=1 # print "j: ",str(j) # si i es menor o igual que j significa que los índices se han cruzado # print "i: ",str(i), ", j: ",str(j), " --> números: ", L if i<=j: # creamos una variable temporal para guardar el valor de L[j] x = L[j] # intercambiamos los valores de L[j] y L[i] L[j] = L[i] L[i] = x # incrementamos y decrementamos i y j respectivamente i+=1 j-=1 # print "L cambiado: ",L,"añadidos i e j: ",str(i),",",str(j) # si first es menor que j mantenemos la recursividad if first < j: L = quicksort(L, first, j) # si last es mayor que i mantenemos la recursividad if last > i: L = quicksort(L, i, last) # devolvemos la lista ordenada return L # Función de búsqueda dicotómica """ def busquedaDicotomica (L,aguja,desde,hasta): i = (desde+hasta)/2 # valor intermedio. while L[i]!=aguja: print "Voy buscando índices...: %d --> %d" % (i,L[i]) if L[i]>aguja: # está en el lado de valores más pequeños hasta = i-1 elif L[i]<aguja: # está en el lado de valores mayores desde = i+1 i = (desde+hasta)/2 # valor intermedio. Recalculo. return i """ # Función de búsqueda dicotómica RECURSIVA def busquedaDicotomica (L,aguja,desde,hasta): ans = -1 # En principio, la respuesta es -1 if desde>=hasta: ans = -1 # Si los dos índices se encuentran, o el inferior supera al superior, es que no ha encontrado nada else: centro = (desde+((hasta-desde)//2)) # calculo el centro... // cociente de la división if aguja < L[centro]: ans = busquedaDicotomica(L,aguja,desde,centro) # Busco en la parte del array inferior. No poner centro-1 ?? elif aguja > L[centro]: ans = busquedaDicotomica(L,aguja,centro+1,hasta) # busco en la parte del array superior else: ans = centro # Y si lo encuentra, es la respuesta return ans # ================== # Programa principal # ================== # Genero un vector con 20 elementos colocados en posiciones aleatorias, de números entre 1 y 100 numeroDeElementos = 70 maximoNumeroAparecido = 100 misNumeros = [] for i in range(1,maximoNumeroAparecido+1): longitud = len(misNumeros) misNumeros.insert(random.randint(0,longitud),i) misNumeros = misNumeros[:numeroDeElementos] # solo quiero 20 números print "Mis números: ",misNumeros print "= = = " print "Pero ahora los ordeno... " misNumeros = quicksort(misNumeros,0,len(misNumeros)-1) print "Ordenados: ",misNumeros # =========================================================================== # Búsqueda dicotómica # ¿En qué lugar encuentro uno de los números? # Uso búsqueda secuencial cuando la lista no es ordenada o no puedo ordenarla # Método más lento. No queda más remedio que recorrer uno a uno. # =========================================================================== numeroAleatorio = misNumeros[random.randint(0,len(misNumeros)-1)] # numeroAleatorio = 43 print "El número elegido es el %d" % (numeroAleatorio) indiceEncontrado = busquedaDicotomica(misNumeros,numeroAleatorio,0,len(misNumeros)-1) if indiceEncontrado!=-1: print "El valor buscado se encuentra en el lugar...: %d" % (indiceEncontrado) print "Compruebo... %d" % (misNumeros[indiceEncontrado]) else: print "No encontrado" # print quicksort(misNumeros,0,len(misNumeros)-1)
= = =
Algoritmo para insertar un dato en un array ordenado
Búsqueda por dicotomía: modificación para insertar un elemento.
Uso el programa anterior, modificado, para conseguir insertar un elemento en un array ordenado en su posición.# *-* coding: utf-8 *-*
import random
def quicksort(L, first, last):
# definimos los índices y calculamos el pivote
i = first
j = last
pivote = (L[i] + L[j]) / 2
# print "PIVOTE: ",str(pivote)
# iteramos hasta que i no sea menor que j
while i < j:
# iteramos mientras que el valor de L[i] sea menor que pivote
while L[i] < pivote:
# Incrementamos el índice
i+=1
# print "i: ",str(i)
# iteramos mientras que el valor de L[j] sea mayor que pivote
while L[j] > pivote:
# decrementamos el índice
j-=1
# print "j: ",str(j)
# si i es menor o igual que j significa que los índices se han cruzado
# print "i: ",str(i), ", j: ",str(j), " --> números: ", L
if i<=j:
# creamos una variable temporal para guardar el valor de L[j]
x = L[j]
# intercambiamos los valores de L[j] y L[i]
L[j] = L[i]
L[i] = x
# incrementamos y decrementamos i y j respectivamente
i+=1
j-=1
# print "L cambiado: ",L,"añadidos i e j: ",str(i),",",str(j)
# si first es menor que j mantenemos la recursividad
if first < j:
L = quicksort(L, first, j)
# si last es mayor que i mantenemos la recursividad
if last > i:
L = quicksort(L, i, last)
# devolvemos la lista ordenada
return L
# Función de búsqueda dicotómica RECURSIVA
# Modificación para que devuelva, de todas formas, aunque no lo encuentre, la posición.
def busquedaDicotomica (L,aguja,desde,hasta):
if desde>=hasta:
ans = hasta # Si los dos índices se encuentran, o el inferior supera al superior, es que no ha encontrado nada
else:
centro = (desde+((hasta-desde)//2)) # calculo el centro... // cociente de la división
if aguja < L[centro]:
ans = busquedaDicotomica(L,aguja,desde,centro) # Busco en la parte del array inferior. No poner centro-1 ??
elif aguja > L[centro]:
ans = busquedaDicotomica(L,aguja,centro+1,hasta) # busco en la parte del array superior
else:
ans = centro # Y si lo encuentra, es la respuesta
return ans
# ==================
# Programa principal
# ==================
# Genero un vector con 20 elementos colocados en posiciones aleatorias, de números entre 1 y 100
numeroDeElementos = 15
maximoNumeroAparecido = 100
misNumeros = []
for i in range(1,maximoNumeroAparecido+1):
longitud = len(misNumeros)
misNumeros.insert(random.randint(0,longitud),i)
numeroInsertar = misNumeros[numeroDeElementos]
misNumeros = misNumeros[:numeroDeElementos] # solo quiero 20 números
print "Mis números: ",misNumeros
print "Número a insertar... ",numeroInsertar
print "= = = "
print "Pero ahora los ordeno... "
misNumeros = quicksort(misNumeros,0,len(misNumeros)-1)
print "Ordenados: ",misNumeros
# ================================================================================================
# Búsqueda dicotómica e Inserción
# ¿En qué lugar encuentro uno de los números? ¿Dónde introduzco otro?
# Uso búsqueda secuencial c# *-* coding: utf-8 *-*
import random
def quicksort(L, first, last):
# definimos los índices y calculamos el pivote
i = first
j = last
pivote = (L[i] + L[j]) / 2
# print "PIVOTE: ",str(pivote)
# iteramos hasta que i no sea menor que j
while i < j:
# iteramos mientras que el valor de L[i] sea menor que pivote
while L[i] < pivote:
# Incrementamos el índice
i+=1
# print "i: ",str(i)
# iteramos mientras que el valor de L[j] sea mayor que pivote
while L[j] > pivote:
# decrementamos el índice
j-=1
# print "j: ",str(j)
# si i es menor o igual que j significa que los índices se han cruzado
# print "i: ",str(i), ", j: ",str(j), " --> números: ", L
if i<=j:
# creamos una variable temporal para guardar el valor de L[j]
x = L[j]
# intercambiamos los valores de L[j] y L[i]
L[j] = L[i]
L[i] = x
# incrementamos y decrementamos i y j respectivamente
i+=1
j-=1
# print "L cambiado: ",L,"añadidos i e j: ",str(i),",",str(j)
# si first es menor que j mantenemos la recursividad
if first < j:
L = quicksort(L, first, j)
# si last es mayor que i mantenemos la recursividad
if last > i:
L = quicksort(L, i, last)
# devolvemos la lista ordenada
return L
# Función de búsqueda dicotómica RECURSIVA
# Modificación para que devuelva, de todas formas, aunque no lo encuentre, la posición.
def busquedaDicotomica (L,aguja,desde,hasta):
if desde>=hasta:
ans = hasta # Si los dos índices se encuentran, o el inferior supera al superior, es que no ha encontrado nada
else:
centro = (desde+((hasta-desde)//2)) # calculo el centro... // cociente de la división
if aguja < L[centro]:
ans = busquedaDicotomica(L,aguja,desde,centro) # Busco en la parte del array inferior. No poner centro-1 ??
elif aguja > L[centro]:
ans = busquedaDicotomica(L,aguja,centro+1,hasta) # busco en la parte del array superior
else:
ans = centro # Y si lo encuentra, es la respuesta
return ans
# ==================
# Programa principal
# ==================
# Genero un vector con 20 elementos colocados en posiciones aleatorias, de números entre 1 y 100
numeroDeElementos = 15
maximoNumeroAparecido = 100
misNumeros = []
for i in range(1,maximoNumeroAparecido+1):
longitud = len(misNumeros)
misNumeros.insert(random.randint(0,longitud),i)
numeroInsertar = misNumeros[numeroDeElementos]
misNumeros = misNumeros[:numeroDeElementos] # solo quiero 20 números
print "Mis números: ",misNumeros
print "Número a insertar... ",numeroInsertar
print "= = = "
print "Pero ahora los ordeno... "
misNumeros = quicksort(misNumeros,0,len(misNumeros)-1)
print "Ordenados: ",misNumeros
# ================================================================================================
# Búsqueda dicotómica e Inserción
# ¿En qué lugar encuentro uno de los números? ¿Dónde introduzco otro?
# Uso búsqueda secuencial cuando la lista no es ordenada o no puedo ordenarla
# Método más lento. No queda más remedio que recorrer uno a uno.
# EN ESTE CASO LA MODIFICO PARA ENCONTRAR EL INDICE SUPERIOR DEL ELEMENTO DONDE TENGO QUE INSERTAR
# ================================================================================================
# numeroAleatorio = misNumeros[random.randint(0,len(misN umeros)-1)]
print "El número elegido es el %d" % (numeroInsertar)
indiceEncontrado = busquedaDicotomica(misNumeros,numeroInsertar,0,len(misNumeros)-1)
if misNumeros[indiceEncontrado]==numeroInsertar:
print "El valor buscado se encuentra en el lugar...: %d" % (indiceEncontrado)
print "Compruebo... %d" % (misNumeros[indiceEncontrado])
print "No necesito insertarlo..."
else: print "El límite superior está en el índice... %d" % (indiceEncontrado)
print "Antes del valor... %d" % (misNumeros[indiceEncontrado])
misNumeros.insert(indiceEncontrado,numeroInsertar) # Al insertar en esa posición, se desplazan los demás a la derecha...
print "Array con elemento insertado: %s" % (misNumeros)
uando la lista no es ordenada o no puedo ordenarla
# Método más lento. No queda más remedio que recorrer uno a uno.
# EN ESTE CASO LA MODIFICO PARA ENCONTRAR EL INDICE SUPERIOR DEL ELEMENTO DONDE TENGO QUE INSERTAR
# ================================================================================================
# numeroAleatorio = misNumeros[random.randint(0,len(misN umeros)-1)]
print "El número elegido es el %d" % (numeroInsertar)
indiceEncontrado = busquedaDicotomica(misNumeros,numeroInsertar,0,len(misNumeros)-1)
if misNumeros[indiceEncontrado]==numeroInsertar:
print "El valor buscado se encuentra en el lugar...: %d" % (indiceEncontrado)
print "Compruebo... %d" % (misNumeros[indiceEncontrado])
print "No necesito insertarlo..."
else: print "El límite superior está en el índice... %d" % (indiceEncontrado)
print "Antes del valor... %d" % (misNumeros[indiceEncontrado])
misNumeros.insert(indiceEncontrado,numeroInsertar) # Al insertar en esa posición, se desplazan los demás a la derecha...
print "Array con elemento insertado: %s" % (misNumeros)
No hay comentarios:
Publicar un comentario