Como está nos comentários e na outra resposta, dicionários em Python são uma tabela de hash, com tempo de busca O(1) - e a informação sobre isso está aqui: https://docs.python.org/3/faq/design.html#how-are-dictionaries-implemented
Dito isso, sobre o design de código que você pergunta - chave in dict
vs dict[chave]
: o tempo de acesso é o mesmo - só que se a chave não existir, a segunda forma levanta uma exceção.
Quando você vai recupear um valor que não tem certeza se existe no dicionário o recomendado é usar o método .get
:
meu_valor = dicionario.get("chave")
Nesse caso, se "chave" não existir, o .get
retorna None e a vida continua. O .get
também aceita um segundo parâmetro que é o retornado quando a chave não existe, em vez de None.
Isso economiza linhas de código - do tipo
if chave in dicionario:
valor = dicionario[chave]
else:
valor = None
ou
try:
valor = dicionario[chave]
except KeyError:
valor = None
Desses, esse segundo caso seria o único que teria alguma diferença de performance, por conta do tempo de criação do contexto do try/except .
Veja também o método .setdefault
dos dict
s: eles não só recuperam um valor padrão caso não exista um - mas nesse caso, fazem a atribuição do novo valor. Por exemplo, um loop para criar um dicionário com todas as palavras de um texto e a posição de cada palavra dentro do mesmo, numa lista, poderia ser:
palavras = texto.split()
posicoes = {}
for indice, palavra in enumerate(palavras):
posicoes.setdefault(palavra, []).append(indice)
Nesse caso, se a palavra ainda não foi encontrada, é criada uma lista vazia que é ao mesmo tempo atribuida lá e retornada pelo método. Se posicoes[palavra]
já existe, a lista existente é retornada.
Agora, já que você se interessa por isso e quer saber sobre busca binária, aqui vai o fato interessante: o Python tem uma interface bem definida para objetos do tipo "Mapping" - e é bme tranquilo implementar um objeto que se comporte exatamente como um dicionário, mas com os algoritmos internos que você decidir. Se você quiser criar um dicionário que internamente seja uma árvore binária, é bem fácil - a forma recomendada de se fazer isso é herdar a classe collections.abc.MutableMapping
. Há várias classes em collections.abc
que são a base para implementar estruturas de dados bem uteis e variadas. Uma árvore binaria teria busca O(log(n)), mas com a vantagem de você poder ter ordenação das chaves e poder usar slices na mesma, por exemplo. Confira em: https://docs.python.org/3/library/collections.abc.html
Eu tenho vários "superdicionários" implementados no módulo extradict
- alguns são mais de brinquedo, outros eu uso mesmo em produção:
https://github.com/jsbueno/extradict