Quando usar o Fibonacci Search
Uma estratégia de busca elegante que usa a sequência de Fibonacci para dividir arrays ordenados de forma eficiente — sem operações de divisão.
Técnico em Eletrônica · Estruturas de Dados e Algoritmos
O que é o Fibonacci Search?
O Fibonacci Search é um algoritmo de busca para arrays ordenados, proposto em 1953 por Jack Kiefer. Ele é parente próximo da busca binária, mas em vez de dividir o array sempre ao meio, usa os números da sequência de Fibonacci para decidir onde comparar.
Em sistemas onde multiplicação e divisão são custosas — como certos microcontroladores e processadores embarcados usados em eletrônica — o Fibonacci Search é vantajoso porque utiliza apenas adição e subtração para calcular as posições de comparação.
Isso torna o algoritmo interessante para projetos de sistemas embarcados, firmware e situações onde se quer evitar a divisão inteira que a busca binária exige.
Revisando a sequência de Fibonacci
A sequência de Fibonacci é formada somando os dois números anteriores:
Cada número Fib(k) = Fib(k-1) + Fib(k-2). No algoritmo, mantemos três números de Fibonacci consecutivos ao mesmo tempo: fib2, fib1 e fib0, onde fib2 = fib1 + fib0.
Como o algoritmo funciona
Dado um array ordenado de n elementos e um valor alvo x:
Passo 1 — Inicialização
Encontre o menor número de Fibonacci maior ou igual a n. Chame-o de fib2. Defina também fib1 (o anterior) e fib0 (o anterior ao anterior). Inicialize offset = -1.
Passo 2 — Loop de comparação
Enquanto fib2 > 1, calcule o índice de comparação:
i = min(offset + fib1, n - 1)
arr[i] < x → alvo à direita. Descarte a metade inferior. Avance: fib2 ← fib1, fib1 ← fib0, offset ← i.
arr[i] > x → alvo à esquerda. Descarte a metade superior. Recue: fib2 ← fib0, reduza fib1 e fib0.
arr[i] = x → encontrado no índice i. Fim.
Passo 3 — Verificação final
Quando fib2 = 1, há um último elemento a verificar. Se arr[offset+1] = x, encontrado. Caso contrário, o valor não está no array.
Exemplo passo a passo
Array: [2, 5, 8, 13, 21, 34, 38, 42, 55, 67] (n = 10). Buscando o valor 42.
O menor Fibonacci ≥ 10 é 13. Logo: fib2=13, fib1=8, fib0=5. Offset = -1.
| Passo | fib2 / fib1 / fib0 | i | arr[i] | Decisão |
|---|---|---|---|---|
| 1 | 13 / 8 / 5 | min(-1+8, 9) = 7 | 42 | ✓ Encontrado no índice 7! |
Valor 42 encontrado no índice 7 com apenas 1 comparação. A busca binária também acharia em 1 passo aqui, mas o Fibonacci chegou ao ponto correto sem divisão.
Agora buscando 55 no mesmo array:
| Passo | fib2 / fib1 / fib0 | i | arr[i] | Decisão |
|---|---|---|---|---|
| 1 | 13 / 8 / 5 | 7 | 42 | 42 < 55 → avança. offset=7 |
| 2 | 8 / 5 / 3 | min(7+5,9) = 9 | 67 | 67 > 55 → recua |
| 3 | 5 / 3 / 2 | min(7+3,9) = 9 | 67 | 67 > 55 → recua |
| 4 | 2 / 1 / 1 | min(7+1,9) = 8 | 55 | ✓ Encontrado no índice 8! |
Implementação em Python
def fibonacci_search(arr, x): n = len(arr) # Gera os três Fibonacci consecutivos iniciais fib0 = 0 # Fib(k-2) fib1 = 1 # Fib(k-1) fib2 = 1 # Fib(k) # Avança até fib2 >= n while fib2 < n: fib0 = fib1 fib1 = fib2 fib2 = fib1 + fib0 offset = -1 # Marca a posição anterior ao intervalo atual while fib2 > 1: i = min(offset + fib1, n - 1) if arr[i] < x: # Alvo à direita: descarta metade inferior fib2 = fib1 fib1 = fib0 fib0 = fib2 - fib1 offset = i elif arr[i] > x: # Alvo à esquerda: descarta metade superior fib2 = fib0 fib1 = fib1 - fib0 fib0 = fib2 - fib1 else: return i # Encontrado! # Verifica o último elemento restante if fib1 and arr[offset + 1] == x: return offset + 1 return -1 # Não encontrado # Teste arr = [2, 5, 8, 13, 21, 34, 38, 42, 55, 67, 72, 89, 91] resultado = fibonacci_search(arr, 42) print(f"Índice encontrado: {resultado}") # Saída: 7
Complexidade e comparação
| Algoritmo | Melhor caso | Caso médio | Pior caso |
|---|---|---|---|
| Fibonacci Search | O(1) | O(log n) | O(log n) |
| Busca Binária | O(1) | O(log n) | O(log n) |
| Busca Linear | O(1) | O(n) | O(n) |
O Fibonacci Search tende a fazer mais comparações na parte inicial do array (proporção áurea ≈ 61,8%). Isso favorece a localidade de cache em memórias sequenciais, como memórias flash em microcontroladores, onde acessos próximos ao início são mais rápidos.
Quando usar o Fibonacci Search?
Use quando:
- O array está ordenado e cabe na memória.
- O processador não tem instrução de divisão (ex: microcontroladores PIC, AVR de baixo custo).
- O acesso à memória é sequencial ou tem custo variável por posição.
- Você quer explorar as propriedades da razão áurea em projetos educacionais.
Não use quando:
- O array não está ordenado (use busca linear ou ordene antes).
- O array muda com frequência (prefira estruturas como árvores balanceadas).
- A divisão inteira é nativa e barata no hardware (a busca binária já é suficiente).
Conexão com a eletrônica
No curso técnico em eletrônica, você vai lidar com microcontroladores como Arduino (AVR) e ESP32. Algoritmos de busca aparecem em situações práticas como:
- Tabelas de lookup (LUT): converter leituras de ADC em valores de temperatura ou tensão — a tabela é ordenada e o Fibonacci Search encontra o intervalo de interpolação.
- Menus de firmware: navegar em listas de comandos armazenados em flash.
- Análise de sinais digitais: buscar um limiar específico em um buffer de amostras ordenadas.
No Arduino (ATmega328P), a divisão de inteiros de 16 bits consome vários ciclos de clock. Em loops críticos com tabelas grandes, trocar a busca binária pelo Fibonacci Search pode reduzir o tempo de busca em ~10–15% dependendo do tamanho da tabela.
Resumo
| Característica | Valor |
|---|---|
| Tipo | Busca em array ordenado |
| Complexidade de tempo | O(log n) |
| Espaço extra | O(1) — in-place |
| Operações necessárias | Apenas + e − |
| Pré-requisito | Array ordenado |
| Ideal para | Hardware sem divisão, memórias sequenciais |
Técnico em Eletrônica · Algoritmos de Busca · Fibonacci Search (Kiefer, 1953)
Estudante de Eletrônica - SENAI RS
© 2026 | Registro de Estudos e Projetos Técnicos
Comentários
Postar um comentário