Algoritmos em Busca de Vetores

1 Introdução à Computação II – 5954006 Introdução à Computação II 5954006 4. Algoritmos de Busca em Vetores Prof. Renato Tinós Local: Depto. de Computação e Matemática (FFCLRP/USP) 2 Introdução à Computação II – 5954006 4.1. Introdução 4.2. Busca Linear 4.2.1. Busca Linear Padrão 4.2.2. Busca Linear com Sentinela 4.3. Busca Binária 4.3.1. Busca Binária Padrão 4.3.2. Busca Binária Rápida Principais Tópicos 3 Introdução à Computação II – 5954006 • Existem diversas aplicações computacionais que devem lidar com uma grande quantidade de dados  Exemplo: processamento de dados provenientes de transações bancárias • Busca (ou pesquisa) visa  Recuperar informação a partir de uma massa de informações previamente armazenada Encontrar uma ou mais ocorrências de registros com chaves iguais às chaves de busca 4.1. Introdução 4 Introdução à Computação II – 5954006 • O conjunto de registros é normalmente chamado de  Tabela Termo geralmente associado a entidades de vida curta – Exemplo: dados na memória principal durante a execução de um problema  Arquivo Termo geralmente associado a entidades de vida longa – Exemplo: dados armazenados na memória secundária 4.1. Introdução 5 Introdução à Computação II – 5954006 • Nos processos de busca tratados neste curso, deve-se buscar um registro (estrutura em C) composto de  Dados Informações  Chave 4.1. Introdução ... typedef struct { tipo chave; // chave de busca ... // demais informações } item ; ... item a[N]; ... 6 Introdução à Computação II – 5954006 4.1. Introdução • No processo de busca, o conjunto de dados, entre os quais o registro que deve ser procurado, possui tamanho fixo  Exemplo item a[N]; • Objetivo da busca  Encontrar o item com a chave igual à chave de busca dada Exemplo – a[i].chave == chave_de_busca 7 Introdução à Computação II – 5954006 • Por simplicidade, considere que  o tipo item é um vetor de inteiros no qual os elementos são as chaves  a chave de busca é um inteiro  N é uma constante que indica o número de elementos do vetor • Assim, objetivo da busca se resume a encontrar o índice i do elemento vetor[i] que é igual à chave de busca chave_de_busca 4.1. Introdução 8 Introdução à Computação II – 5954006 Exemplo 4.1. Dado um vetor a, buscar o índice do elemento igual à chave x  Busca de x = 19, retorna i = 5  Busca de x = 45, retorna i = 0  Busca de x = 8, retorna i = 6  Busca de x = 43, retorna i = 3 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a 4.1. Introdução 9 Introdução à Computação II – 5954006 Exemplo 4.1. Dado um vetor a, buscar o índice do elemento igual à chave x  Busca de x = 81? Depende da implementação Pode, por exemplo, retornar i = -1 se a busca não teve êxito 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a 4.1. Introdução 10 Introdução à Computação II – 5954006 4.2.1. Busca Linear Padrão • Busca Linear ou Busca Seqüencial  Utilizada quando não há informações adicionais sobre os dados a serem pesquisados  A busca linear termina quando for satisfeita uma das seguintes condições 1. O elemento é encontrado 2. Todo o vetor foi analisado  Exemplo de algoritmo de busca linear ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... 11 Introdução à Computação II – 5954006 Exemplo 4.2. Busca de x = 12 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a i 8 N 0 i ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... 4.2.1. Busca Linear Padrão 12 Introdução à Computação II – 5954006 Exemplo 4.2. Busca de x = 12 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a i 8 N 0 i ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... V V 4.2.1. Busca Linear Padrão 13 Introdução à Computação II – 5954006 Exemplo 4.2. Busca de x = 12 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a i 8 N 1 i ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... 4.2.1. Busca Linear Padrão 14 Introdução à Computação II – 5954006 Exemplo 4.2. Busca de x = 12 ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... V V 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a i 8 N 1 i 4.2.1. Busca Linear Padrão 15 Introdução à Computação II – 5954006 Exemplo 4.2. Busca de x = 12 ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a i 8 N 2 i 4.2.1. Busca Linear Padrão 16 Introdução à Computação II – 5954006 Exemplo 4.2. Busca de x = 12 • Término do laço: Se i ≠ N então x foi encontrado na posição i do vetor ... i  0 enquanto ( i < N e a[i] ≠ x ) i  i + 1 fim enquanto ... 0 1 2 3 4 5 6 7 45 56 12 43 95 19 8 67 a i 8 N 2 i V F 4.2.1. Busca Linear Padrão 17 Introdução à Computação II – 5954006 • Análise do algoritmo  Em média são efetuadas N/2 comparações de chaves – quando a chave existe na tabela e chaves podem ocorrer com mesma probabilidade  Melhor caso 1 comparação, i.e., O(1)  Pior caso requer N comparações de chaves A complexidade de tempo é O(N) 4.2.1. Busca Linear Padrão 18 Introdução à Computação II – 5954006 4.2.2. Busca Linear com Sentinela • Simplificação da expressão Booleana  Introdução de um elemento adicional no final do vetor Um elemento é sempre retornado  Retira necessidade de verificar se chegou no fim do vetor 19 Introdução à Computação II – 5954006 • Exemplo de algoritmo de busca linear com sentinela  Ao final do laço, i = N implica que o elemento com chave x não foi encontrado 4.2.2. Busca Linear com Sentinela ... declare a[N+1] ... i  0 a[N]  x enquanto ( a[i] ≠ x ) i  i + 1 fim enquanto ... 20 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a i 8 N 0 i ... i  0 a[N]  x enquanto (a[i] ≠ x ) i  i + 1 fim enquanto ... Exemplo 4.3. Busca de x = 56 4.2.2. Busca Linear com Sentinela 21 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a i 8 N 0 i ... i  0 a[N]  x enquanto (a[i] ≠ x ) i  i + 1 fim enquanto ... Exemplo 4.3. Busca de x = 56 56 Sentinela 4.2.2. Busca Linear com Sentinela 22 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a i 8 N 0 i ... i  0 a[N]  x enquanto (a[i] ≠ x ) i  i + 1 fim enquanto ... Exemplo 4.3. Busca de x = 56 56 Sentinela 4.2.2. Busca Linear com Sentinela V 23 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a i 8 N 1 i ... i  0 a[N]  x enquanto (a[i] ≠ x ) i  i + 1 fim enquanto ... Exemplo 4.3. Busca de x = 56 56 Sentinela 4.2.2. Busca Linear com Sentinela 24 Introdução à Computação II – 5954006 0 1 2 3 4 5 6 7 8 45 56 12 43 95 19 8 67 a i 8 N 1 i ... i  0 a[N]  x enquanto (a[i] ≠ x ) i  i + 1 fim enquanto ... Exemplo 4.3. Busca de x = 56 56 Sentinela 4.2.2. Busca Linear com Sentinela F 25 Introdução à Computação II – 5954006 4.2.2. Busca Linear com Sentinela • Análise do algoritmo  Em média são efetuadas (N+1)/2 comparações de chaves – quando a chave existe na tabela e chaves podem ocorrer com mesma probabilidade  Melhor caso 1 comparação, i.e., O(1)  Pior caso requer N+1 comparações de chaves A complexidade de tempo é O(N) – Entretanto, o número de operações primitivas para a versão com Sentinela é menor que a versão padrão para N acima de uma determinada constante 27 Introdução à Computação II – 5954006 4.3. Busca Binária • Não é possível acelerar a busca sem que se disponha de maiores informações sobre a organização do vetor  Para o caso geral, o problema de busca tem complexidade de tempo O(N) • No entanto, é possível alcançar uma eficiência maior se informações adicionais sobre o vetor estiverem disponíveis • Por exemplo, considere que os as chaves estejam ordenadas  Exemplo: de forma crescente, ou seja a[0] ≤ a[1] ≤ … ≤ a[N-1] 28 Introdução à Computação II – 5954006 • Neste caso, pode se implementar a busca binária • A idéia principal é comparar a chave de um registro qualquer da seqüência (por exemplo, um registro no meio da seqüência) com a chave de busca x • Se chave de busca for  igual à chave do registro  a busca termina  maior que a chave do registro, conclui-se que todos os elementos com índices menores ou iguais ao índice do registro podem ser eliminados nos próximos passos  menor que a chave do registro, todos aqueles elementos com índices maiores ou iguais ao índice do registro podem ser eliminados nos próximos passos 4.3. Busca Binária 29 Introdução à Computação II – 5954006 • Embora a escolha do ponto do início da busca (m no algoritmo exemplificado) possa ser arbitrária, já que o algoritmo funciona independentemente dele, o valor desta variável influencia diretamente a eficiência do algoritmo • Para a solução ótima, deve-se eliminar o maior número possível de elementos em futuras buscas  Assim, a solução ótima é escolher um elemento no meio (ou mais próximo possível do meio) da seqüência 4.3.1. Busca Binária Padrão 30 Introdução à Computação II – 5954006 Exemplo 4.4. Simule o processo de busca binária para x = 78 4.3.1. Busca Binária Padrão 0 1 2 3 4 5 6 7 5 6 12 23 45 59 78 97 a 31 Introdução à Computação II – 5954006 4.3.1. Busca Binária Padrão • Exemplo de algoritmo de busca binária ... L  0 R  N - 1 sucesso  0 enquanto ( ( L ≤ R ) e ( sucesso = 0 ) ) m  floor( (R+L)/2 ) se ( a[m] = x ) sucesso  1 senão se ( a[m] < x ) L  m + 1 senão R  m – 1 fim se fim se fim enquanto ... 32 Introdução à Computação II – 5954006 Exemplo 4.5. Simule o processo de busca binária para x = 7 4.3.1. Busca Binária Padrão 0 1 2 3 4 5 6 7 5 6 12 23 45 59 78 97 a 33 Introdução à Computação II – 5954006 • A eficiência pode ser ligeiramente melhorada se o sucesso (término) da busca não for testado em todo loop  Lembre-se que sucesso ocorre apenas uma vez em todo o processo • Além disso, pode-se abandonar a meta de terminar a busca no instante exato em que for encontrado o elemento pesquisado  Isso parece pouco inteligente à primeira vista, mas observando-se mais a fundo, pode-se constatar que o ganho em eficiência em cada passo será maior do que a perda ocasionada pela comparação de alguns poucos elementos adicionais 4.3.2. Busca Binária Rápida 34 Introdução à Computação II – 5954006 • Exemplo de algoritmo de busca binária rápida  Se ao término do loop, a condição a[R] = x for satisfeita, então o elemento procurado foi encontrado na posição R  Caso contrário, o elemento não foi encontrado 4.3.2. Busca Binária Rápida ... L  0 R  N - 1 enquanto ( L < R ) m  floor( (R+L)/2 ) se ( a[m] < x ) L  m + 1 senão R  m fim se fim enquanto ... 35 Introdução à Computação II – 5954006 Exemplo 4.6. Simule o processo de busca binária rápida para x = 78 0 1 2 3 4 5 6 7 5 6 12 23 45 59 78 97 a 4.3.2. Busca Binária Rápida 36 Introdução à Computação II – 5954006 • Análise do número de comparações entre chaves  No início, o número de elementos a ser examinado é N . Dividindo por dois até que reste apenas um elemento, teremos 1=N/2p sendo p o número de divisões  O número de comparações de chaves em um conjunto com N registros é aproximadamente log2(N) 4.3.2. Busca Binária Rápida 37 Introdução à Computação II – 5954006 • Análise  O pior caso requer log2 N comparações Portanto a complexidade de tempo é O(log2 N) N Nº Comparações (pior caso) 8 3 128 7 1.024 10 32.768 15 1.048.576 20 1080 266 4.3.2. Busca Binária Rápida 38 Introdução à Computação II – 5954006 • Análise  Considerando os algoritmos de busca vistos, a tabela seguinte mostra a ordem de grandeza dos números mínimo (Cmín), médio (Cméd) e máximo (Cmáx) de comparações de chaves Algoritmo Cmín Cméd Cmáx Busca Linear O (1) O (N) O (N) Busca Linear com Sentinela O (1) O (N) O (N) Busca Binária O (1) O (log2N) O (log2N) Busca Binária Rápida O (log2N) O (log2N) O (log2N) 4.3.2. Busca Binária Rápida 39 Introdução à Computação II – 5954006 Busca Binária Busca Linear Número de elementos (N) Número de comparações 4.3.2. Busca Binária Rápida