🚀 O Plus para Programadores Iniciantes: Pesquisa Binária em Python! 💡
def pesquisa_binaria(lista, item_procurado):
inicio = 0
fim = len(lista) - 1
while inicio <= fim:
meio = (inicio + fim) // 2
if lista[meio] == item_procurado:
return meio
elif lista[meio] < item_procurado:
inicio = meio + 1
else:
fim = meio - 1
return None
numeros = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
resultado = pesquisa_binaria(numeros, 7)
A pesquisa binária é um dos algoritmos fundamentais da ciência da computação. Quer você saiba ou não, já o utilizou em vários momentos. Muitos algoritmos que inserem em coleções ordenadas também usam a pesquisa binária. É especialmente útil no contexto de uma 'árvore binária balanceada', permitindo busca e inserção em O(log2(n)). A maioria das linguagens fornece alguma estrutura como essa, por exemplo, o std::map.
Outro algoritmo de pesquisa fundamental que todo programador deve conhecer é o hash. É a implementação padrão de dicionários em Python e objetos em JavaScript. O hashing permite uma busca quase instantânea O(1). Uma das grandes desvantagens do Hash é não permitir o acesso sequencial aos dados de forma eficiente.
Uma evolução da árvore binária é a B-tree. Criada para resolver efetivamente o problema de evitar rotações do disco rigido - combinando acesso aleatório em memoria com acesso sequencial - oferece uma busca muito mais rápida em muitos casos. Mesmo considerando memória SSDs, as B-trees também maximizam o uso do cache e de transferencia de IO e tendem a ser mais rápidas. São a estrutura padrão usada por bancos de dados e sistemas de arquivos para recuperação rápida de dados.
Outra otimização na pesquisa binária é usar uma heurística para não dividir exatamente no meio, mas tentar adivinhar para qual lado o alvo está inclinado. Intuitivamente, é o que fazemos ao procurar informações em conjuntos ordenados. Uma estrutura de dados mais avançada que incorpora essa ideia é a lista de saltos (skip list), uma estrutura probabilística que pode rivalizar com hashes e árvores binárias.
Caraka gostei muito do seu material e vou ler com calma e aplicar a um projeto que tenho.
Cara, muito massa! Coincidentemente eu acabei de fazer um trabalho da faculdade, onde o professor pedia para explicarmos um exemplo de pesquisa binária com recursividade.
Caso alguém tenha interesse, aqui está o vídeo (o tempo máximo era 5 mins, então tive que cortar o vídeo bruto de 22 minutos, eliminando muitas coisas):
Obs: O vídeo não está monetizado