Algoritmo de pesquisa binária Python
Pesquise listas classificadas em tempo logarítmico O (log n). Execute e entenda a pesquisa binária em Python, incluindo lógica passo a passo, casos extremos e otimizações.
Visão geral
A pesquisa binária é um algoritmo excepcionalmente eficiente para encontrar um item em uma lista ordenada. Ao contrário da pesquisa linear que varre cada elemento sequencialmente em tempo O(n), a pesquisa binária funciona dividindo repetidamente o intervalo de pesquisa pela metade.
A pesquisa começa examinando o elemento intermediário do array. Se o valor alvo corresponder ao elemento intermediário, sua posição será retornada. Se o alvo for menor, o algoritmo restringe sua busca à metade inferior; se o alvo for maior, ele o estreitará para a metade superior. Este processo se repete até que o elemento seja encontrado ou o tamanho do subarray caia para zero.
Para implementar a pesquisa binária em Python, usamos dois ponteiros (baixo e alto) para rastrear os limites da pesquisa ativa. Como o espaço de busca diminui pela metade a cada passo, o algoritmo é executado em tempo O(log n), tornando-o ideal para bancos de dados massivos.
Saída de código e execução
Uma implementação de pesquisa binária iterativa padrão que retorna o índice de um elemento de destino em uma lista classificada.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23
index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
print(f"Target found at index: {index}")
else:
print("Target not found in dataset")Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5Implementação passo a passo
- Consultar indexação e pesquisa em tabelas de banco de dados
- Encontrar valores limites ou limites em intervalos matemáticos contínuos
- Funções de preenchimento automático e pesquisa em campos de texto
Perguntas frequentes
A lista precisa ser classificada para que a pesquisa binária funcione?
Sim, a pesquisa binária depende estritamente dos elementos que estão sendo classificados. Se a lista não estiver classificada, a lógica de comparação será interrompida e você deverá classificar a lista primeiro ou usar uma pesquisa linear.
Por que usar a pesquisa binária iterativa em vez da pesquisa binária recursiva?
Embora a pesquisa binária recursiva seja elegante, a pesquisa binária iterativa é frequentemente preferida na produção. A abordagem iterativa é executada no espaço auxiliar O(1), enquanto a pesquisa recursiva ocupa o espaço O(log n) devido à pilha de chamadas, arriscando o estouro da pilha em entradas extremamente grandes.
Tópicos Relacionados
Explore algoritmos de classificação python. Visualize a classificação por bolha e a classificação por mesclagem nativamente em um contexto IDE do navegador.
Tutorial do algoritmo Python Merge SortAprenda como implementar Merge Sort em Python. Um exemplo interativo passo a passo da estratégia de classificação Dividir e Conquistar.
Guia do algoritmo Python QuicksortExplore o algoritmo quicksort em Python. Aprenda seleção dinâmica, particionamento e recursão neste exemplo de codificação interativo.