Aula 35 – Busca Binária, Exclusão e Programa Completo

Busca Binária — Dividindo para Conquistar

A busca sequencial examina até n elementos. A busca binária divide o problema pela metade a cada passo — examine apenas log₂(n) elementos. Para 1024 elementos: sequencial faz até 1024 comparações; binária faz no máximo 10.

Visualizando a Busca Binária — Procurando o 7

Lista ordenada: [1, 3, 4, 7, 9, 12, 15] — procurando ch = 7:

Procurando ch = 12 na mesma lista:

Procurando ch = 6 (não existe):

A Função buscaBinaria

int buscaBinaria(LISTA* l, TIPOCHAVE ch) {
    int ini  = 0;
    int fim  = l->nroElem - 1;

    while (ini <= fim) {
        int meio = (ini + fim) / 2;

        if (ch == l->A[meio].chave) return meio;  // achou!

        if (ch < l->A[meio].chave)
            fim = meio - 1;  // chave está na metade esquerda
        else
            ini = meio + 1;  // chave está na metade direita
    }
    return -1;  // ini > fim: chave não existe na lista
} /* buscaBinaria */

Exclusão de Elemento

Excluir um elemento é o inverso da inserção: encontramos o índice do elemento, depois deslocamos todos os elementos subsequentes uma posição para a esquerda, sobrescrevendo o elemento excluído, e decrementamos nroElem.

bool excluirElemLista(LISTA* l, TIPOCHAVE ch) {
    int pos = buscaSequencial(l, ch);  // encontra a posição
    if (pos == ERRO) return false;      // elemento não existe

    int j;
    for (j = pos; j < l->nroElem - 1; j++)
        l->A[j] = l->A[j + 1];        // desloca para a esquerda

    l->nroElem--;
    return true;
} /* excluirElemLista */

Visualizando: excluir o elemento com chave 12 da lista [9, 3, 12, 4, 1]:

Reinicializar a Lista

Zerar a lista sem liberar memória (afinal, em lista estática não há memória dinâmica para liberar):

void reinicializarLista(LISTA* l) {
    l->nroElem = 0;  // apenas zera o contador — os dados no array são "esquecidos"
} /* reinicializarLista */

Programa Completo — Tudo Integrado

O main() completo que exercita todas as funções que aprendemos nas aulas 29 a 35:

int main() {
    LISTA lista;
    inicializarLista(&lista);
    exibirLista(&lista);

    printf("Nro elementos: %d\n", tamanho(&lista));
    printf("Tamanho bytes: %d\n", tamanhoEmBytes(&lista));

    REGISTRO reg;
    reg.chave = 9;  inserirElemLista(&lista, reg, 0);
    exibirLista(&lista);   // Lista: " 9 "

    reg.chave = 3;  inserirElemLista(&lista, reg, 1);
    reg.chave = 4;  inserirElemLista(&lista, reg, 2);
    reg.chave = 1;  inserirElemLista(&lista, reg, 3);
    reg.chave = 12; inserirElemLista(&lista, reg, 2);
    exibirLista(&lista);   // Lista: " 9 3 12 4 1 "

    printf("Nro elementos: %d\n", tamanho(&lista));
    printf("Tamanho bytes: %d\n", tamanhoEmBytes(&lista));

    printf("Chave 4, pos: %d\n", buscaSequencial(&lista, 4));
    printf("Chave 4, pos: %d\n", buscaSentinela(&lista, 4));

    if (excluirElemLista(&lista, 4))  printf("Excluído: 4\n");
    if (excluirElemLista(&lista, 8))  printf("Excluído: 8\n");  // não existe
    if (excluirElemLista(&lista, 9))  printf("Excluído: 9\n");
    exibirLista(&lista);   // Lista: " 3 12 1 "

    printf("Nro elementos: %d\n", tamanho(&lista));

    reinicializarLista(&lista);
    exibirLista(&lista);   // Lista: ""
    printf("Nro elementos: %d\n", tamanho(&lista));

    return 0;
}

Resumo do Bloco — Aulas 29 a 35