Algunos ejercicios de TDA I.
[z.facultad/75.29/ejercicios.git] / busquedaternaria.py
1 #!/usr/bin/env python
2
3 import sys
4
5 def buster(lista, valor):
6
7         def busrec(ini, fin):
8                 if ini >= fin:
9                         try:
10                                 if lista[ini] == valor:
11                                         return ini
12                         except IndexError:
13                                 if lista[fin] == valor:
14                                         return fin
15                         return None
16                 seg = (fin - ini) / 3
17                 a = ini + seg
18                 b = a + seg
19                 if a == b:
20                         b += 1
21                 if valor == lista[a]:
22                         return a
23                 if valor < lista[a]:
24                         return busrec(ini, a - 1)
25                 if valor == lista[b]:
26                         return b
27                 if valor < lista[b]:
28                         return busrec(a + 1, b - 1)
29                 return busrec(b + 1, fin)
30
31         return busrec(0, len(lista))
32
33
34 print dict([(i, int(n)) for i, n in enumerate(sys.argv[2:])]), int(sys.argv[1])
35 print buster([int(n) for n in sys.argv[2:]], int(sys.argv[1]))
36
37 # Orden:
38 #
39 # T(N) = 1 * T(N/3) + O(1)  (A = 1, B = 3, k = 0)
40 #
41 # => O(T(N)) = O(N^0 * log3 N) = O((1 / log 3) * log N) = O(log N)