Ciências da computação dia 168

Durante nossa aula de hoje, exploramos dois métodos fundamentais para buscar elementos em um conjunto de dados: a busca linear e a busca binária. Além disso, introduzimos o conceito de recursão, uma técnica poderosa que permite resolver problemas dividindo-os em subproblemas menores. Vamos revisar cada tópico com exemplos práticos.

Busca Linear

A busca linear (ou sequencial) é o método mais simples: percorremos o array elemento por elemento até encontrar o valor desejado. Caso o valor não exista, retornamos um indicador de falha.

def busca_linear(arr, x):
    for i, v in enumerate(arr):
        if v == x:
            return i
    return -1

Complexidade: O(n) no pior caso (quando o elemento está no final ou não existe). É adequada para arrays pequenos ou não ordenados.

Busca Binária

A busca binária exige que o array esteja ordenado. Ela funciona dividindo o intervalo de busca pela metade a cada iteração, comparando o elemento do meio com o valor procurado.

def busca_binaria(arr, x, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == x:
        return mid
    elif arr[mid] < x:
        return busca_binaria(arr, x, mid+1, right)
    else:
        return busca_binaria(arr, x, left, mid-1)>

Note que a implementação acima é recursiva. A complexidade é O(log n), muito mais eficiente que a busca linear para grandes conjuntos.

Introdução à Recursão

Recursão ocorre quando uma função chama a si mesma para resolver uma versão menor do mesmo problema. Toda função recursiva precisa de um caso base (que interrompe a recursão) e de uma chamada recursiva que aproxima o problema do caso base.

Exemplo clássico: cálculo do fatorial.

def fatorial(n):
    if n <= 1:
        return 1
    return n * fatorial(n-1)

No caso da busca binária, o caso base é intervalo vazio (left > right), e a chamada recursiva reduz o intervalo pela metade.

Comparação: Busca Linear vs. Busca Binária

Exercícios Práticos

1. Implemente a busca binária de forma iterativa (sem recursão).
2. Modifique o algoritmo de busca linear para retornar todos os índices onde o elemento aparece.
3. Escreva uma função recursiva que calcule o n-ésimo termo da sequência de Fibonacci e compare sua eficiência com uma versão iterativa.

Perguntas Frequentes

Qual a principal vantagem da busca binária sobre a linear?

A busca binária é muito mais rápida em arrays grandes, com complexidade O(log n) contra O(n) da busca linear. No entanto, ela exige que o array esteja ordenado.

A busca binária funciona em listas não ordenadas?

Não. Se a lista não estiver ordenada, o algoritmo pode falhar, pois a decisão de ir para a metade esquerda ou direita depende da comparação com o elemento do meio.

Quando devo usar recursão em vez de iteração?

Recursão é natural para problemas que podem ser decompostos em subproblemas semelhantes, como árvores, grafos e algoritmos de dividir e conquistar. Porém, pode ser menos eficiente em espaço (pilha de chamadas) e deve ser evitada quando há risco de estouro de pilha.

Para mais conteúdos como este, visite a página de posts do blog. Continue praticando e explorando o mundo da ciência da computação!