#1T(n-1)+O(1)
def soma(n):
    if n == 0:
        return -1
    for _ in range(n):
        x = 1
    s = soma(n-1)+n

    return s
#1T(n-3)+O(n)
def soma(n):
    if n == 0:
        return -1
    for _ in range(n):
        x = 1
    s = soma(n-3)+n

    return s
#2T(n-3)+O(n)
def soma(n):
    if n == 0:
        return -1
    for _ in range(n):
        x = 1
    s = soma(n-3)+soma(n-3)+n

    return s
#2T(n/2)+O(n)
def soma(n):
    if n == 0:
        return -1
    for _ in range(n):
        x = 1
    s = soma(n/2)+soma(n/2)+n

    return s

#apresentar os valores de uma lista de forma recursiva
def apresentar(v,i):
    if i < len(v):
        print(v[i])
        apresentar(v,i+1)

v = list(range(10))
print(apresentar(v,0))
#soma os valores de um vetor de forma recursiva
def somar(v,i):
    if i >= len(v):
        return 0
    return somar(v,i+1)+v[i]

v = list(range(10))
print(somar(v,0))

#busca pulando
def busca(v,p):
    i = 0
    contador = 0
    while (i < len(v) and v[i] < p):
        i += 10
        contador += 1

    if i == len(v):
        return -1

    for i in range(i-10,i):
        contador += 1
        if v[i] == p:
            return i,contador

print(busca(list(range(1000)),739))

#busca iterativa
def busca_binaria(v,p):
    inicio = 0
    fim = len(v)-1
    contador = 0

    while (inicio <= fim):
        meio = (inicio+fim)//2
        contador += 1
        if v[meio] == p:
            print(contador)
            return meio
        elif p > v[meio]:
            inicio = meio+1
        else:
            fim = meio - 1
    print(contador)
    return -1

#701 - 1500
#500 - 700
#200 - 499
#100 - 199
#40 - 99
#10 - 39
#< 10


print(busca_binaria(list(range(1000000)),867543))


#busca binaria recursiva
def busca_binaria(v,p,i,f):

    if i > f:
        return -1
    if v[i] == p:
        return i
    if v[i] < p:
        busca_binaria(v,p,m+1,f)
    else:
        busca_binaria(v,p,i,m-1)
1T(n/2) + O(1) = O(log n)
#701 - 1500
#500 - 700
#200 - 499
#100 - 199
#40 - 99
#10 - 39
#< 10


print(busca_binaria(list(range(1000000)),867543))