Algortmo Interpolation Search
Publicado por Nicolás (1 intervención) el 18/04/2018 16:39:58
Hola, intentando hacer el algoritmo de Interpolation Sort
Funciona aparentemente, pero en algunas ocasiones no responde o aparece error "out of index", por ejemplo, si ingreso "1,2,3" y busco "4", aparece out of index ó si por ejemplo ingreso "2,6,13,15" y busco "12" no muestra nada.
Funciona aparentemente, pero en algunas ocasiones no responde o aparece error "out of index", por ejemplo, si ingreso "1,2,3" y busco "4", aparece out of index ó si por ejemplo ingreso "2,6,13,15" y busco "12" no muestra nada.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def interpolationSearch(a, x):
lowerBound = 0upperBound = len (a) -1
index = -1
part1 = (upperBound - lowerBound)
part2 = (int (a[upperBound]) - int (a[lowerBound]))
part3 = int (x) - int (a[lowerBound])
while lowerBound < upperBound:
middlePoint = int (lowerBound + (part1 / part2) * part3)
if x == a[middlePoint]:
index = middlePointbreak
elif x < a[middlePoint]:
upperBound = middlePoint -1
else:lowerBound = middlePoint + 1
if lowerBound == upperBound and a[lowerBound] == x:
index = lowerBoundreturn index
print ("Ingrese números: ")
a = input()
print ("Ingrese número a buscar: ")
x = input()
list = a.split(",")
indice = interpolationSearch(list, x)
if (indice >= 0):
print ("El número está en el índice: ", indice, "\n")
else:print ("El número no se encontró.\n")
Valora esta pregunta
0