O que é pesquisar
Pesquisa é recuperar informação em um grande volume de dados. A informação é dividida em registros; cada registro tem uma chave que o identifica; o objetivo é encontrar o registro (ou os registros) cuja chave é igual à chave dada.
| Aplicação | Chave |
|---|---|
| Conta bancária | número da conta |
| Reserva aérea | localizador |
| Histórico escolar | matrícula |
O restante do registro — nome, saldo, notas — é dado satélite: viaja junto, mas a pesquisa só olha a chave.
A estrutura que guarda esses itens e suporta inserir, remover e pesquisar tem três nomes na literatura: tabela de símbolos (compiladores), dicionário (chave \(\to\) item) e conjunto dinâmico (CLRS, Parte III). “Dinâmico” porque ele muda: cresce e encolhe durante a execução.
O TAD e a escolha do método
Os métodos de pesquisa são tratados como TADs: um conjunto de operações, independente de como a estrutura é implementada.
- Pesquisar registro(s) com chave \(k\)
- Mínimo / máximo
- Sucessor / antecessor
- Listar em ordem
- Inicializar
- Inserir um novo registro
- Remover um registro
Cada aplicação usa só algumas delas — e é isso que decide a melhor implementação. Dois critérios pesam: a quantidade de dados e a frequência de inserções e remoções, isto é, se a tabela é estática ou dinâmica.
| Método | Quando |
|---|---|
| Sequencial 1D | hoje |
| Sequencial 2D (linhas e Hilbert) | hoje |
| Binária 1D | hoje |
| Binária 2D | hoje |
| Árvores de pesquisa | mais adiante |
| Hashing | mais adiante |
A ideia e a estrutura
O método mais simples: olhar um registro de cada vez. Os registros ficam em um vetor, sem ordem nenhuma.
- Pesquisar: a partir do primeiro, compara até achar a chave ou acabar o vetor.
- Inserir: adiciona no final do vetor.
- Remover: localiza o item e coloca o último no lugar dele.
Inserir e remover (depois de achar) custam \(O(1)\) — só porque não há ordem a manter. Guarde isso: é exatamente o que a binária vai perder.
Na estrutura, Item[1..n] guarda os registros e \(n\) é quantos há; Item[0] fica reservado para a sentinela — por isso o vetor é declarado com MAX + 1 posições para MAX registros. Pesquisa devolve a posição do registro, ou 0 se ele não existe.
A sentinela
A versão direta percorre Item[1..n] comparando um a um e faz dois testes por iteração: o limite i <= n e a comparação de chaves. O teste de limite dá para eliminar.
/* retorna 0 se nao encontrar */int Tabela::Pesquisa(TipoChave x) {Item[0].Chave = x; // sentinelaint i = n + 1;do {i--;} while (Item[i].Chave != x);return i;}
A linha 3 copia a chave procurada para a posição 0, o que garante que a chave existe no vetor. O teste de limite i >= 1 vira desnecessário e o laço passa a testar uma coisa só: “achei?”. Se o laço parou em \(i=0\), o que ele achou foi a sentinela — a chave não está na tabela.
Traço das duas pesquisas
| posição | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| chave | sentinela | 23 | 7 | 41 | 15 | 9 |
Pesquisa(41): escreve 41 em Item[0] e desce de \(i=5\): compara 9, depois 15, depois 41 — para em \(i=3\) e retorna 3, com 3 comparações.
Pesquisa(8): escreve 8 em Item[0] e desce comparando 9, 15, 41, 7, 23 e por fim o próprio 8 da sentinela — para em \(i=0\) e retorna 0: não está, com \(n+1\) comparações.
No insucesso o laço nunca passa da posição 0: é a sentinela que garante que ele para.
Análise e balanço
Contando as comparações de chave Item[i].Chave != x:
| Situação | Comparações | Por quê |
|---|---|---|
| sucesso, melhor caso | 1 | a chave está em Item[n] |
| sucesso, pior caso | \(n\) | a chave está em Item[1] |
| sucesso, caso médio | \(\dfrac{n+1}{2}\) | cada posição igualmente provável |
| insucesso | \(n+1\) | percorre tudo e ainda testa a sentinela |
O caso médio sai da soma das posições:
$$\frac{1}{n}\sum_{i=1}^{n} i = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}$$Em todos os casos relevantes, \(\Theta(n)\): dobrar a tabela dobra o tempo.
A favor: é simples de acertar, não exige ordem nenhuma nos dados e tem inserção e remoção \(O(1)\) — ótima para tabelas pequenas. Contra: com \(10^6\) registros são \(\sim500\) mil comparações por consulta em média, e o insucesso é o pior caso sempre.
Dá para melhorar em duas direções, e a aula segue as duas: mudar o percurso na memória (2D e Hilbert) ou usar a ordem das chaves (pesquisa binária).
A localidade da sequencial
Na instrumentação da A5 — tabela de 64 registros e uma sequência de pesquisas, \(\approx 540\) acessos — cada dente de serra do mapa é uma pesquisa: os endereços crescem um a um a partir do início do vetor.
Localidade espacial ótima, porque os acessos são contíguos. Mas cada pesquisa revisita o vetor inteiro, e o reuso de um registro acontece longe do acesso anterior: distância de pilha média 36,6 em 542 reusos, com pico perto de 60, o tamanho da tabela. Espacial boa, temporal ruim.
Sequencial 2D por linhas
Com os registros numa matriz \(dim\times dim\), pesquisar percorre registro a registro, inserir usa a próxima posição livre e remover põe o último no lugar. Muitos dados são 2D — imagens, grades, tabuleiros — e aí o percurso vira decisão de projeto.
int Tabela::Pesquisa(TipoChave x) {for (int i = 0; i < dim; i++)for (int j = 0; j < dim; j++)if (Mat[i][j].Chave == x)return i * dim + j;return -1; // nao achou}
Com \(n = dim^2\) itens o custo é \(O(n)\), igual ao vetor, e a linha 5 converte \((i,j)\) na posição linear. A localidade também é igual: por linhas, a matriz é percorrida como um vetor, na ordem da memória (row-major, A5). Medindo numa matriz \(8\times8\) com as mesmas pesquisas, a distância média dá 40,0 em 572 reusos — a faixa do vetor 1D. Sequencial por linhas em 2D \(\approx\) sequencial em 1D, nas duas métricas.
A curva de Hilbert
Uma space-filling curve mapeia a matriz 2D em uma única dimensão. A de Hilbert tem duas famílias de propriedades:
- Localidade espacial: pontos próximos na matriz ficam próximos na representação 1D; cada passo vai a uma célula vizinha (cima, baixo, esquerda, direita), sem saltos; e cada célula é visitada exatamente uma vez, sem cruzamentos.
- Estrutura fractal e recursiva: divide a matriz em 4 quadrantes em forma de “U”, e cada quadrante é rotacionado e refletido recursivamente. Exige \(dim\) potência de 2.
int Tabela::Pesquisa(TipoChave x) {int lin, col;for (int i = 0; i < n; i++) {Hilbert_d2xy(n, i, &lin, &col);if (Mat[lin][col].Chave == x)return i;}return -1; // nao achou}
A linha 4 converte a posição \(i\) na curva para as coordenadas \((lin,col)\); o laço continua \(O(n)\). No mapa, o dente de serra dá lugar a blocos — a curva fica um tempo em cada quadrante antes de mudar. Distância média 33,6 em 503 reusos: melhor que por linhas (40,0) e que o vetor 1D (36,6).
A ideia
Adivinhar um número entre 1 e 100 chutando 1, 2, 3… gasta 99 palpites, porque cada chute elimina um número. Chutando 50, depois 75, depois 63, cada palpite elimina metade do que sobrou — \(100\to50\to25\to13\to7\to4\to2\to1\), no máximo 7 palpites. É como se procura uma palavra no dicionário: abrindo no meio.
- Compare a chave \(x\) com o elemento do meio do vetor.
- Igual? achou. Menor? só a metade esquerda interessa. Maior? só a direita.
- Repita na metade escolhida até achar — ou até a metade ficar vazia.
Pré-condição: só funciona se as chaves estiverem ordenadas. É o que permite descartar metade sem olhar para ela.
Os dois exemplos do quadro
| posição | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| chave | A | A | A | C | E | E | E | G | H | I | L | M | N | P | R |
1. \(meio=8\): G \(<\) L \(\Rightarrow\) vai para a direita, sobra H I L M N P R.
2. \(meio=12\): M \(>\) L \(\Rightarrow\) vai para a esquerda, sobra H I L.
3. \(meio=10\): I \(<\) L \(\Rightarrow\) vai para a direita, sobra L.
4. \(meio=11\): L \(=\) L, achou.
4 comparações para 15 elementos — a sequencial gastaria até 15. O intervalo cai pela metade a cada passo: \(15\to7\to3\to1\).
Mesma tabela. \(meio=8\): G \(<\) K, direita. \(meio=12\): M \(>\) K, esquerda. \(meio=10\): I \(<\) K, direita. \(meio=11\): L \(>\) K, esquerda — intervalo vazio: K não está.
O insucesso é detectado quando o limite esquerdo ultrapassa o direito. Também 4 comparações: na binária, o insucesso não degrada — ao contrário da sequencial, em que ele é o pior caso.
O código
int TabelaBinaria::Pesquisa(TipoChave x) {if (n == 0) return 0;int mid, Esq = 1, Dir = n;do {mid = Dir - ((Dir - Esq) / 2);if (x > Item[mid].Chave)Esq = mid + 1; // metade direitaelseDir = mid - 1; // metade esquerda} while ((x != Item[mid].Chave) && (Esq <= Dir));if (x == Item[mid].Chave) return mid;return 0;}
[Esq..Dir] é o intervalo onde \(x\) ainda pode estar. A linha 5 calcula o meio; as linhas 6–9 decidem de que lado continuar; a linha 10 mantém o laço enquanto não achou e ainda há elementos; e as duas últimas descobrem por qual dos dois motivos o laço parou.
Análise: \(\Theta(\lg n)\) por dois caminhos
A cada iteração o intervalo cai pela metade: \(n \to n/2 \to n/4 \to \dots \to 1\). Quantas vezes dá para dividir \(n\) por 2 até chegar a 1? \(\lg n\) vezes. Pior caso: \(\lfloor \lg n\rfloor + 1\) comparações — para \(n=15\), \(3+1=4\), exatamente o que os dois exemplos gastaram.
Um subproblema de tamanho \(n/2\), custo constante fora da recursão. Com \(a=1\) e \(b=2\), o marco é \(n^{\log_b a}=n^0=1\); como \(f(n)=\Theta(1)=\Theta(n^{\log_b a})\), é o caso 2:
$$T(n)=\Theta\!\left(n^{\log_b a}\lg n\right)=\Theta(\lg n)$$| \(n\) | sequencial (pior) | binária (pior) |
|---|---|---|
| 15 | 15 | 4 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
| \(8\times10^9\) (população da Terra) | \(8\times10^9\) | 33 |
Dobrar \(n\) custa uma comparação a mais. Num dicionário de 240 000 palavras: 18 passos, contra até 240 000 lendo uma por uma.
O preço: manter o vetor ordenado
| posição | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| chave | 3 | 7 | 12 | 15 | 18 | 25 | 31 | 40 |
Para o 15 entrar na posição 4, os registros 18, 25, 31 e 40 são deslocados uma posição cada.
Inserir (ou remover) na posição \(p\) desloca todos os registros de \(p\) em diante: \(O(n)\) por operação, e inserir \(n\) registros um a um vira comportamento quadrático. Se todas as chaves estão disponíveis no início, ordene uma vez — \(O(n\lg n)\), tema das próximas aulas — e pesquise à vontade.
Pesquisa binária é ideal para tabelas estáticas; não deve ser usada em aplicações muito dinâmicas.
A localidade da binária
São \(\approx 85\) acessos no total, contra \(\approx 543\) da sequencial. Cada pesquisa toca o meio, depois um quarto, depois um oitavo — pontos que se repetem entre pesquisas. Distância média 6,4 em 84 reusos, contra 36,6 da sequencial: uma ordem de grandeza.
A binária reduz o valor das distâncias e a frequência das distâncias grandes. Ela ganha nas duas métricas da aula: comparações (\(n \to \lg n\)) e localidade.
Por que só um quarto morre
A pré-condição agora é dupla: chaves ordenadas por linhas e por colunas — crescem para a direita e para baixo. Compara-se \(x\) com o elemento central da submatriz:
- \(x < \text{centro}\)? \(x\) não pode estar no quadrante inferior-direito (tudo ali é \(\ge\) centro): descarte-o.
- \(x > \text{centro}\)? descarte o quadrante superior-esquerdo.
Recursão nos 3 quadrantes restantes.
Exemplo passo a passo
Pesquisa(19) na matriz \(5\times5\) do quadro
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 2 | 5 | 9 | 16 | 20 |
| 1 | 4 | 8 | 14 | 21 | 26 |
| 2 | 7 | 13 | 22 | 27 | 34 |
| 3 | 11 | 19 | 25 | 31 | 40 |
| 4 | 15 | 24 | 30 | 38 | 45 |
Escolha do meio — o meio do intervalo vivo em cada eixo:
$$m_r = t + \left\lfloor \frac{b-t}{2} \right\rfloor$$ $$m_c = l + \left\lfloor \frac{r-l}{2} \right\rfloor$$Com \([0..4]\times[0..4]\): \(m_r=m_c=0+\lfloor 4/2\rfloor = 2 \Rightarrow M[2][2]=22\), e \(19<22\).
Descarte garantido só no inferior-direito, onde tudo é \(\ge 22\): morrem 9 das 25 células, \(\approx 1/4\). Os outros três sobrevivem por razões diferentes — o superior-esquerdo é todo \(\le 22\), o “lado certo” da comparação; o superior-direito e o inferior-esquerdo misturam os dois lados do centro (\(9<22<26\) e \(7<22<24\)), então qualquer chave \(<22\) pode estar neles.
Código e análise
[t..b] × [l..r] é a submatriz vivaint bin2d(Reg M[][MAX], TipoChave x,int t, int l, int b, int r) {if (t > b || l > r) return 0;int mr = t + (b - t) / 2;int mc = l + (r - l) / 2;TipoChave c = M[mr][mc].Chave;if (c == x) return 1;if (x < c) // mata inferior-direitoreturn bin2d(M, x, t, l, mr-1, r)|| bin2d(M, x, mr, l, b, mc-1);else // mata superior-esquerdoreturn bin2d(M, x, mr+1, l, b, r)|| bin2d(M, x, t, mc+1, mr, r);}
A linha 3 trata a submatriz vazia; as linhas 4–6 acham o centro; e os dois retângulos das linhas 9–10 são, juntos, exatamente os 3 quadrantes que sobram — as linhas 12–13 fazem o caso simétrico.
Cada comparação elimina \(1/4\) da submatriz e sobram 3 subproblemas com \(n/4\) células:
$$T(n) = 3\,T\!\left(\frac{n}{4}\right) + \Theta(1)$$O marco é \(n^{\log_4 3}\approx n^{0,79}\) e \(f(n)=\Theta(1)=O(n^{\log_4 3 - \varepsilon})\) \(\Rightarrow\) caso 1:
$$T(n)=\Theta\!\left(n^{\log_4 3}\right)\approx\Theta\!\left(n^{0,79}\right)$$Sublinear, mas bem pior que o \(\Theta(\lg n)\) do 1D. A intuição em uma linha: em 1D uma comparação mata \(1/2\); em 2D, só \(1/4\).
\(\approx 126\) acessos, contra \(\approx 570\) da sequencial 2D, com distância média 10,7 em 125 reusos. Os acessos ficam espalhados pela matriz — a recursão salta entre quadrantes —, então a localidade espacial é pior que a da binária 1D; mas o volume de acessos despenca.
O dilema e o quadro final
| Estrutura | Pesquisa | Inserção | Exige |
|---|---|---|---|
| Sequencial | \(O(n)\) | \(O(1)\) | nada |
| Binária | \(O(\lg n)\) | \(O(n)\) | vetor ordenado |
| Árvore de pesquisa | \(O(\lg n)\) | \(O(\lg n)\) | mais adiante |
Cada uma é boa onde a outra é ruim, e a culpa é do vetor: contíguo, toda inserção no meio empurra o resto. A saída são as árvores de pesquisa, mais adiante. Antes delas, a pergunta óbvia — de onde vem o vetor ordenado? — abre a ordenação, a partir da próxima aula. Os cinco métodos de hoje, lado a lado:
| Método | Comparações (pior) | DP média\(^*\) | Pré-requisito |
|---|---|---|---|
| Sequencial 1D | \(n\) | 36,6 | nenhum |
| Sequencial 2D (linhas) | \(n\) | 40,0 | nenhum |
| Sequencial 2D (Hilbert) | \(n\) | 33,6 | \(dim\) potência de 2 |
| Binária 1D | \(\lfloor\lg n\rfloor + 1\) | 6,4 | vetor ordenado |
| Binária 2D | \(\Theta(n^{0,79})\) | 10,7 | linhas e colunas ordenadas |
\(^*\) medida na instância dos slides: 64 registros, mesma sequência de pesquisas.
Três ideias para levar: ordem descarta sem olhar — metade em 1D, um quadrante em 2D; mesma complexidade não é mesmo desempenho — o percurso é decisão de projeto, é a lição de Hilbert; e a binária vence nas duas métricas, comparações (\(n\to\lg n\)) e distância de pilha (36,6 \(\to\) 6,4).
Armadilhas comuns
| Armadilha | O que acontece |
|---|---|
| Binária em vetor não ordenado | o resultado é silenciosamente errado — nenhum erro de execução avisa |
mid = (Esq + Dir) / 2 | com \(n\) perto de \(2^{31}\) a soma estoura o int; use Esq + (Dir - Esq)/2, ou a forma do código da aula |
| Binária 2D com ordem só nas linhas | o descarte de quadrante exige linhas e colunas ordenadas; ordenar cada linha isoladamente não basta |
| Achar que mesmo \(O(\cdot)\) é mesmo desempenho | a sequencial 2D por colunas faz as mesmas comparações e pula \(dim\) registros por acesso — localidade péssima em row-major |
| Hilbert em matriz de dimensão qualquer | a curva exige \(dim\) potência de 2; caso contrário é preciso completar (padding) |
| Vetor ordenado + inserções frequentes | cada inserção desloca \(O(n)\) registros; a manutenção da ordem vira o gargalo |
Os exercícios do quadro
| Exercício | Resposta |
|---|---|
| 1. Contas. Com \(n=10^6\) chaves ordenadas, quantas comparações a binária faz no pior caso? | \(\lfloor \lg 10^6\rfloor + 1 = 20\) |
| 2. Recursiva. Escreva a binária recursiva, monte a recorrência e resolva pelo Teorema Mestre. | \(T(n)=T(n/2)+\Theta(1)\), caso 2 \(\Rightarrow \Theta(\lg n)\) |
3. Percurso. Troque os dois for da sequencial 2D (colunas por fora). O que muda nas comparações? E no mapa de acesso e nas distâncias de pilha? Esboce o mapa esperado antes de rodar. | a fazer |
| 4. Binária 2D. Verifique que os dois retângulos do código cobrem exatamente os 3 quadrantes restantes e resolva \(T(n)=3T(n/4)+\Theta(1)\). | caso 1 \(\Rightarrow \Theta(n^{\log_4 3})\approx\Theta(n^{0,79})\) |
| 5. Desafio (escada). Na matriz ordenada por linhas e colunas, comece no canto superior direito: se o elemento é maior que \(x\), ande para a esquerda; se é menor, desça. Mostre que isso pesquisa com \(O(dim)=O(\sqrt n)\) comparações. | a fazer |
Checklist da A6
Se você consegue responder tudo abaixo sem consultar, a aula está fechada.
| Pergunta | Onde está |
|---|---|
| Listar as operações de um dicionário e separar consultas de modificações | O tipo abstrato de dados |
| Escrever a pesquisa sequencial com sentinela e dizer o que ela economiza | A sentinela |
Traçar Pesquisa(x) com sucesso e com insucesso, contando comparações | Traço das duas pesquisas |
| Deduzir o caso médio \((n+1)/2\) pela soma das posições | Análise e balanço |
| Dizer por que o percurso por linhas em 2D tem a localidade do vetor 1D | Sequencial 2D por linhas |
| Explicar o que a curva de Hilbert melhora — e o que ela não melhora | A curva de Hilbert |
| Executar a binária passo a passo, com sucesso e com insucesso | Os dois exemplos do quadro |
| Obter \(\Theta(\lg n)\) pelo desenho e pela recorrência | Análise: \(\Theta(\lg n)\) |
| Justificar por que a binária só serve a tabelas estáticas | O preço: manter a ordem |
| Explicar por que na binária 2D só \(1/4\) da submatriz morre | Por que só um quarto morre |
| Montar e resolver \(T(n)=3T(n/4)+\Theta(1)\) | Código e análise |
| Comparar os cinco métodos pelas duas métricas da aula | O dilema e o quadro final |
Escrever mid na forma que não estoura o int | Armadilhas comuns |