Busca Sequencial e Binaria em Arranjos-Metodos de Busca em Codigos de Alta Performance

1 Métodos de Busca em Arranjos de Elementos Códigos de Alta Performance PROFa PATRÍCIA MAGNA profpatriciamagnafiapcombr Motivação 2 Um arquivo é formado por um conjunto de registros Um registro é um conjunto de informações relacionadas entre si A cada registro de uma coleção de registros associase uma chave que é uma informação que distingue aquele registro dos demais Se a chave somente ocorre uma vez na coleção é chamada chave primária No caso da possibilidade de múltiplas ocorrências de uma chave esta é dita chave secundária 3 Método ou Função de Busca ou de Pesquisa Aceita uma chave como argumento Tenta descobrir um registro cuja chave seja coincidente com este argumento e retorna registro encontrado ou um ponteiro para o mesmo Sinalização na condição de inexistência de um registro com a chave recebida 4 Escolha do método Escolha do melhor algoritmo é função de Quantidade de dados Arquivo com a inserçõesremoções frequentes Se o arquivo for estável ou seja que sofre pouco operações de inserção e remoção de dados é preferível minimizar o tempo de pesquisa mesmo que para isso gastese muito tempo para organizar o arquivo 5 Algoritmos de Pesquisa ou Busca A escolha do melhor algoritmo depende muitas vezes do estado de ordenação do arquivo Tipos mais comuns de algoritmos de busca Busca Sequencial Exaustiva Busca Sequencial Busca Binária Busca Sequencial Exaustiva 7 Busca Sequencial Exaustiva A técnica de busca mais simples é a varredura sequencial exaustiva da coleção de registros Percorrese o conjunto até o final independentemente da descoberta de registro ou registros que satisfaçam à condição de busca A chave procurada pode não ser chave primária Procurando todas as ocorrências da palavra NERD em um livro 8 Exemplo de Função Busca Sequencial Exaustiva public static int buscaSequencialExaustivaRegistro bd int chave Registro encontrados int i ne 0 int num bdlength for i 0 i num i if bdichave chave encontradosne bdi armazena registro da posição em que a chave foi encontrada ne return ne quantidade de registros com a chave procurada Projeto MétodosBusca pacote BuscaExaustiva 9 Considerações sobre o Algoritmo É um método simples de se implementar Não necessita de hierarquização ou ordenação prévias Pode ser aplicado para dados em memória e em dispositivos auxiliares como HDs As demais técnicas de busca tentam melhorar a eficiência do processo por meio da redução do conjunto de dados verificado baseadas em algum conhecimento sobre os dados e seu armazenamento se pressupostos forem falhos invalidam o resultado da pesquisa Busca Sequencial Busca Sequencial 11 Algoritmo básico que o arquivo seja varrido sequencialmente até que seja encontrada a chave pesquisada normalmente uma chave primária ou seja única no sistema Se chave não encontrada é atingido o final do arquivo 12 Função de Busca Sequencial public static int buscaSequencialRegistro baseDados int chaveproc int pos 1 for int i 0 i baseDadoslength pos 1 i ifbaseDadosigetChave chaveproc pos i return pos Projeto MétodosBusca pacote BuscaSequencial 13 Considerações sobre o Método Métodos simples de ser implementado mas podem ser feitas melhorias em um sistema que faz muitas pesquisas buscas Cada vez que um registro é procurado ele seria movido para o início do arquivo Se o registro for novamente procurado então ele seria mais rapidamente encontrado Busca Binária Idéia Geral do Método Binary search steps 0 37 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Low mid high Sequential search steps 0 37 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 wwwpenjeecom 16 Idéia Geral do Método É usado para arquivos ORDENADOS Comparase a chave com o elemento central do conjunto Se forem iguais o registro foi encontrado caso contrário o processo será repetido na metade inferior ou na metade posterior conforme o resultado da comparação Volta à comparação até que o registro seja encontrado ou se conclua pela sua inexistência 17 Função para Busca Binária public static int buscaBinariaRegistro baseDados int chaveproc SystemoutprintlnProcurando o chave solicitada int ibaixo 0 int imedio 0 int ialto baseDadoslength 1 boolean achou false int posicao 1 while achou ibaixo ialto imedio ibaixo ialto2 if chaveproc baseDadosimediogetChave posicao imedio achou true else if chaveproc baseDadosimediogetChave ialto imedio 1 else ibaixo imedio 1 return posicao Projeto MétodosBusca pacote buscaBinaria 18 Considerações sobre o Método Métodos simples de ser implementado que necessita de ordenação do arquivo Tem execução muito mais eficiente que a busca sequencial Como saber quanto esse método é mais eficiente em relação ao outro Vamos fazer uma análise de desempenho Como É o que vamos estudar a seguir 19 Eficiência de um Algoritmo Como considerar se algoritmo é mais eficiente que um outro Tempo de execução porém este deve variar com a máquina onde o programa está sendo executado Ocupação de espaço na memória se esta é menor é possível utilizar em dispositivos com quantidade de memória reduzida 20 Eficiência de um Algoritmo Portanto existes esses 2 aspectos de eficiência considerados tempo requerido e espaço de armazenamento Geralmente o programador deverá otimizar um aspecto às custas do outro 21 Como analisar a Eficiência de um Algoritmo A medida de tempo seria dado pelo número de operações críticas efetuadas durante a execução do algoritmo a fim de resolver um específico problema por exemplo a busca de um registro em um arquivo O tamanho do arquivo no qual o algoritmo atua sempre é referenciado em relação à quantidade n de registros que o compõe 22 Quais são as operações críticas São as operações essenciais que deve ser realizadas para resolução do aplicação Exemplos de operações críticas Para algoritmos de busca seriam apenas as comparações sobre chaves Para algoritmos de soma de vetores seriam apenas as adições sobre os elementos dos vetores Para algoritmos de ordenação seriam as comparações sobre chaves e movimentação de registros ou trocas Etc 23 Executando o programa de Comparação entre Métodos Projeto ComparacaoMetodosBusca n sequencial binária 8 8 4 16 16 5 32 32 6 64 64 7 128 128 8 256 256 9 512 512 10 1024 1024 11 0 200 400 600 800 1000 1200 0 200 400 600 800 1000 1200 Número de Comparações n Busca sequencial x Binária sequencial binária 24 Como descrever o comportamento dos Métodos Exercícios 25 Supondo a tabela apresentada responda 1 Existe a chave primária Se sim qual 2 Qual método entre os 3 estudados para realizar busca pode ser usado para a Pesquisar produto de um fabricante selecionado b Pesquisar produto selecionando um código 3 Poderia ser usado o método de busca binária no estado em que se encontra a tabela Explique sua decisão 4 Crie um projeto JAVA para fazer o que é pedido nos exercícios 2a 2b e 3 Produto Código Fabricante Preço Un parafuso 623 ABC R 075 prego 133 ABC R 050 martelo 686 XYZ R 3475 alicate 461 W2M R 2250 soldador 201 ABC R 4899 tesoura 732 W2M R 2380 REFERÊNCIAS TENENBAUM AM E outros Estruturas de Dados usando C Makron Books do Brasil Editora Ltda SP PEREIRA S L Estrutura de Dados Fundamentais São Paulo Érica FORBELLONE ALV EBERSPÄCHER HF Lógica de Programação A Construção de Algoritmos e Estruturas de Dados Makron Books São Paulo SP ASCENCIOAFG e ARAÚJO GS Estruturas de Dados Algoritmos Análise da Complexidade e Implementação em JAVA e CC 27 Copyright 2024 Profa Patrícia Magna Todos direitos reservados Reprodução ou divulgação total ou parcial deste documento é expressamente proibido sem o consentimento formal por escrito dos professores