Slide - Algoritmos em Busca de Vetores - 2023-2

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 26 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] 27 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 28 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 29 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 30 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 ... 31 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 32 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 33 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 ... 34 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 35 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 ➢Por simplicidade, considere que N é uma potência de 2 ◼ Dividindo por dois até que reste apenas um elemento, e considerando que p é o número de repetições do laço, ou divisões por 2, teremos: 1=N/2p 2p=N p= log2N ◼ Para o caso geral, temos que o número de comparações de chaves em um conjunto com N registros é aproximadamente log2N, ou seja, a complexidade computacional é O(log2N) 4.3.2. Busca Binária Rápida 36 Introdução à Computação II – 5954006 • Análise ◼ Exemplos N Nº Comparações 8 3 128 7 1.024 10 32.768 15 1.048.576 20 1080 266 4.3.2. Busca Binária Rápida 37 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 4.3.2. Busca Binária Rápida 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) 38 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 39 Introdução à Computação II – 5954006 Exercício 4.1. Sejam os algoritmos de busca binária rápida e busca linear com sentinela. Pede-se: a. Implemente os algoritmos como funções em C++ para vetores de inteiros ordenados. b. Faça um gráfico do tamanho do vetor (N) pelo número de comparações para o caso de chaves de buscas sorteadas aleatoriamente. 4.3.2. Busca Binária Rápida