Departamento

Vetores
Um vetor (= array) é uma estrutura de dados que armazena uma sequência de objetos, todos do mesmo tipo, em posições consecutivas da memória. Esta página estuda os problemas de procurar um objeto em um vetor, inserir um novo objeto no vetor e remover um elemento do vetor. Estes problemas servem de pretexto para exibir exemplos dealgoritmos recursivos e para ilustrar os conceitos de correção, eficiência e elegância de algoritmos. Os três problemas — busca, inserção e remoção — reaparecerão, em outros contextos, nos demais capítulos. Imagine que temos uma longa lista de números (de telefones, por exemplo) armazenada num vetor v. O espaço reservado para o vetor pode ter sido criado pela declaração int v[N];

sendo N uma constante (possivelmente definida por um #define). Se a lista de números está armazenada nas posições 0,1,...,n-1 do vetor, diremos que v[0..n-1] é um vetor de inteiros.

É claro que devemos ter 0 ≤ n ≤ N. Se n == 0, o vetor v[0..n-1] está vazio. Se n == N, o vetor está cheio.

Busca
Dado um inteiro x e um vetor v[0..n-1] de inteiros, o problema da busca consiste em encontrar x em v, ou seja, encontrar um índice k tal que v[k] == x. O problema faz sentido com qualquer n ≥ 0. Se n é 0, o vetor é vazio e portanto essa instância do problema não tem solução.
0 n-1

443 x 222 555 111 333 444 555 666 888 777 888 999 v É preciso começar com uma decisão de projeto: que fazer se x não está no vetor? Adotaremos a convenção de devolver -1 nesse caso (observe que -1 não pertence ao conjunto 0..n-1 de índices "válidos"). Para implementar essa convenção, convém varrer o vetor do fim para o começo:
/* A função recebe x, n >= 0 e v e devolve um índice k em 0..n-1 tal que x == v[k]. Se tal k não existe, devolve -1. */

int busca( int x, int n, int v[]) { int k; k = n-1; while (k >= 0 && v[k] != x) k -= 1; return k; }

Observe como a função é eficiente e elegante. Ela funciona corretamente mesmo quando o vetor está vazio, ou seja,