Salve,
Fizemos uma versão da busca binária recursiva, mas não está funcionando.
Qual é o problema com a função?
def busca_binaria(x, v): '''(numero, list) -> int ou None Recebe um número x e uma lista crescente v de números e retorna um índice m tal que v[m] == x; caso um tal índice não exista a função retorna None. ''' n = len(v) if n == 0: return None # base m = n // 2 if v[m] == x: return m # base if v[m] < x: return busca_binaria(x,v[m+1:]) return busca_binaria(x,v[:m])
Tem dois problemas.
O primeiro é que no caso de x possívelmente estar na segunda metade da lista, a busca é feita recursivamente sem levar em consideração a primeira metade dos elementos. Então na chamada:
if v[m] < x: return busca_binaria(x,v[m+1:])
Seria necessário adicionar m+1 ao resultado:
if v[m] < x: return m + 1 + busca_binaria(x,v[m+1:])
E isso nos leva ao segundo problema.
Se o resultado da chamada não for um inteiro (ou seja, se x não estiver na lista), a função vai tentar somar um inteiro e um None, o que não dá resultado nenhum.
Dessa forma, é importante verificar o resultado antes de devolvê-lo.
Eu acho também importante fazer isso sem repetir a chamada, pois não queremos duplicar o tempo de busca. Por isso, eu guardaria o valor do resultado em uma variável. Então:
if v[m] < x:
search = busca_binaria(x,v[m+1:]) #aqui a gente guarda o valor na memória
if search: #verifica se é um valor não nulo
return m + 1 + search
O primeiro é que no caso de x possívelmente estar na segunda metade da lista,...
Legal! É verdade!
Dessa forma, é importante verificar o resultado antes de devolvê-lo.
Certo!
Eis a nova versão depois das alterações sugeridas.
Tudo bem agora?
Qual o consumo de tempo dessa função?
def busca_binaria(x, v): '''(numero, list) -> int ou None Recebe um número x e uma lista crescente v de números e retorna um índice m tal que v[m] == x; caso um tal índice não exista a função retorna None. ''' n = len(v) if n == 0: return None # base m = n // 2 if v[m] == x: return m # base if v[m] < x: search = busca_binaria(x,v[m+1:]) #aqui a gente guarda o valor na memória if search != None: #verifica se é um valor não nulo return m + 1 + search return busca_binaria(x,v[:m])
Salve,
O que vocês acham da tentativa de implementação recursiva da busca binária que está mais adiante?
O trecho a seguir foi copiado do livro Programming Pearls de Jon Bentley.
Antoine de Saint-Exupéry, the French writer and aircraft designer, said that, "A designer knows he arrived at perfection not when there is no longer anything to add, but when there is no longer anything to take away." More programmers, should judge their work by this criterion.
#----------------------------------------------------------- def busca_binaria(x,v): '''(numero, list) -> int ou None Recebe um número x e uma lista crescente v de números e retorna unm índice m tal que v[m] == x; caso um tal índice não exista a função retorna None. A função é uma implementação da busca binária. ''' n = len(v) m = n // 2 if n == 1: if v[0] != x: return None if v[m] == x: return m if v[m] < x: pos = buscaR(x, v[m+1:]) if pos == None: return None return 1 + m + pos if v[m] > x: return buscaR(x, v[:m])
Bom, fora a chamada recursiva estar com um nome diferente da função(acho que foi erro de digitação), se você chamar a função com a lista vazia (ex: busca_binaria(3,[])) dá erro.
Isso ocorre por que a base foi definida para n == 1, e no caso temos n == 0, o que fura a definição e causa problema ao tentar calcular v[0].
uma solução seria substituir as linhas
if n == 1:
if v[0] != x:
return None
por
if n == 0:
return None
Quanto ao tempo eu fiquei em dúvida. Mas seria algo proporcional ao log de len(v)?
fora a chamada recursiva estar com um nome diferente da função
É verdade.
uma solução seria substituir as linhas.. por
if n == 0:
return None
É verdade, acho que isso resolve o problema.
Quanto ao tempo eu fiquei em dúvida. Mas seria algo proporcional ao log de len(v)?
O consumo de tempo é bem maior que lg n, onde n é o número de elementos na lista no início da primeira chamada.
A razão para isso está na página: https://wiki.python.org/moin/TimeComplexity
Olhando essa página, alguém tem ideia da razão do consumo de tempo não ser logarítmico?
Pelo que entendi da página, a questão é que, quando chamamos a função recursivamente, uma cópia de uma fatia da lista é feita. Segundo a página (item "get slice"), essa operação tem consumo de tempo linear, maior do que logarítmico.
Segundo a página (item "get slice"), essa operação tem consumo de tempo linear, maior do que logarítmico.
Acho que é isso ai.
No pior caso, o consumo de tempo da função é então proporcional ao tempo gasto para copiar as "metades" das listas em cada chamada recursiva (v[m+1:] ou v[:m]).
Esse tempo é proporcional a:
n/2 + n/4 + n/8 + ... ~ n
onde n = len(v).