UFLA

🎓 Aula 09

Ponteiros, Alocação Dinâmica, Busca Binária e Recursão

Prof. Paulo Rettore

Universidade Federal de Lavras

GAC124 — Introdução aos Algoritmos

🎯 Memória e algoritmos de busca

  • Entender endereços e ponteiros.
  • Alocar e desalocar memória com segurança.
  • Comparar busca linear e busca binária.
  • Reconhecer caso base e chamada recursiva.

A aula integra memória e algoritmos: primeiro entendemos onde os dados estão; depois, como procurá-los.

📍 Variável, endereço e ponteiro

int numero = 25;
int* ponteiro = №

cout << numero;    // valor
cout << &numero;   // endereço
cout << *ponteiro; // valor apontado

&

Obtém o endereço.

*

Acessa o valor apontado.

int*

Ponteiro para um inteiro.

🛡️ Ponteiros seguros

int* p = nullptr;

if (p != nullptr) {
    cout << *p;
}

Não desreferencie um ponteiro nulo ou não inicializado. Primeiro verifique se ele aponta para uma região válida.

🧠 Alocação dinâmica

int n;
cin >> n;

int* v = new int[n];
// use v[0] até v[n - 1]

delete[] v;
v = nullptr;

new

Reserva memória durante a execução.

delete[]

Libera um vetor dinâmico.

⚠️ Cuidados com memória

  • Inicialize ponteiros com nullptr quando ainda não apontarem para dados.
  • Não acesse posições fora do limite alocado.
  • Use delete para um elemento e delete[] para um vetor.
  • Depois de liberar, não use o ponteiro como se ainda fosse válido.

A memória reservada com new precisa ser liberada pelo programa.

🔎 Busca linear

int buscaLinear(const int v[], int n, int chave) {
    for (int i = 0; i < n; i++) {
        if (v[i] == chave)
            return i;
    }
    return -1;
}

Funciona em qualquer vetor. No pior caso, pode verificar todas as posições.

⚡ Busca binária: metade por vez

A busca binária exige um vetor ordenado.

  1. Compare a chave com o elemento do meio.
  2. Se forem iguais, termine.
  3. Se a chave for menor, descarte a metade direita.
  4. Se for maior, descarte a metade esquerda.

A cada passo, a região de busca fica aproximadamente pela metade.

🧭 Exemplo de busca binária

v = {1, 4, 5, 10, 16, 19, 20, 27, 30};
chave = 26;

meio = 16  -> 26 é maior
restam: 19, 20, 27, 30
meio = 20  -> 26 é maior
restam: 27, 30
meio = 27  -> 26 é menor
resultado: não encontrado

Sem ordenação, não é possível descartar metades com segurança.

🔁 Recursão: um problema menor

int fatorial(int n) {
    if (n == 0)          // caso base
        return 1;
    return n * fatorial(n - 1);
}

Caso base

Interrompe a recursão.

Passo recursivo

Chama a função com uma entrada menor.

🧩 Busca binária recursiva

int busca(int v[], int inicio, int fim, int chave) {
    if (inicio > fim) return -1;
    int meio = (inicio + fim) / 2;
    if (v[meio] == chave) return meio;
    if (chave < v[meio])
        return busca(v, inicio, meio - 1, chave);
    return busca(v, meio + 1, fim, chave);
}

A função reduz o intervalo a cada chamada e termina quando encontra a chave ou quando o intervalo fica vazio.

🧩 Prática em aula

Em um vetor ordenado, implemente a busca binária e retorne o índice da chave ou -1.

Gabarito orientador: Atualize início, fim e meio até encontrar a chave ou esvaziar o intervalo. Explique o caso base se usar recursão.

📚 Referências e materiais

Use estas fontes para consultas pontuais depois da aula:

Os slides completos, o Campus Virtual e o DREDD continuam sendo as fontes principais da disciplina.

🔎 Busca linear: comparar um por um

Vetor: {4, 9, 2, 7, 5, 1} · chave: 7. A busca linear funciona mesmo sem ordenação.

for (int i = 0; i < n; i++) {
    if (v[i] == chave) return i;
}
return -1;

⚡ Busca binária: descartar metades

Agora o vetor está ordenado: {1, 4, 5, 10, 16, 19, 20, 27, 30} · chave: 26.

while (inicio <= fim) {
    int meio = (inicio + fim) / 2;
    if (v[meio] == chave) return meio;
    if (chave < v[meio]) fim = meio - 1;
    else inicio = meio + 1;
}
return -1;

🔁 Recursão: chamadas e retornos

O caso base interrompe as chamadas; depois, a pilha retorna os resultados.

int fatorial(int n) {
    if (n == 0) return 1;
    return n * fatorial(n - 1);
}

🔗 Complementos online

📌 Resumo da aula

  • Ponteiro armazena endereço; * acessa o valor apontado.
  • new reserva e delete/delete[] liberam memória.
  • Busca binária exige vetor ordenado.
  • Recursão precisa de caso base e redução do problema.

PRÓXIMA AULA

⏭️ Próxima aula

Registros e vetores de registros

Prof. Paulo Rettore

GAC124 — Introdução aos Algoritmos