Baixe o app para aproveitar ainda mais
Prévia do material em texto
OBS: Aula 07 foi exercício para entrega em sala de aula A função da ordenação é otimizar a busca. Define-se pesquisa como a operação que permite encontrar ou concluir que não existe, um dado elemento num conjunto. Existe uma variedade enorme de métodos de pesquisa. Quantidade de dados envolvidos○ Arquivo estar sujeito a inserções e retiradas frequentes.○ A escolha do método de pesquisa mais adequado a determinada aplicação depende principalmente: Busca Sequencial A forma mais simples de encontrar um elemento em uma estrutura de dados é procurar cada elemento do vetor, um a um (busca sequencial). A pesquisa de um elemento pode ser feita um conjunto ordenado ou não. Quando o conjunto não está ordenado, normalmente faz-se uso da busca sequencial até se encontrar o elemento desejado ou concluir que não existe. Função buscaSequencial (n, chave: inteiro; var vet: interio) : inteiro Var i : inteiro i <- 0 se vet[i] = chave) então retorne i; i <- i =1 enquanto (i<n) faça fim enquanto retorne -1 inicio fimfunção Busca binária Encontra o meio do vetor Se for igual, então para○ Se for menor, despreza os elementos à direita do meio○ Se for maior, despreza os elementos à esquerda do meio○ Compara o meio do vetor com o elemento buscado Repete até que o elemento seja encontrado Quando o conjunto está ordenado a busca binária é mais eficiente que a busca sequencial. Pela busca binária, a ideia é reduzir o espaço de busca já que a estrutura está ordenada. função buscaBinária (n, chave: inteiro; ver vet: inteiro) : inteiro esquerda,direita, meio : inteiro var Semana 06 - Aula 08 - Ordenação Externa (Algoritmos de pesquisa sexta-feira, 4 de abril de 2014 19:14 Página 1 de COM112 - Algoritmo e Estrutura de Dados II esquerda,direita, meio : inteiro esquerda <- 0 direita <- n-1 meio = (esquerda + direita) / 2 retorne meio se (vet[meio = chave) esquerda = meio +1 Se (vet[meio] < chave) direita = meio - 1 senao fimse senao fimsenão enquanto (esquerda <= direita) fimequanto inicio fimfunção Para estruturas com variáveis diferentes criam-se índices para cada campo para facilitar a busca de acordo com o campo utilizado. Se estiver ordenada pela informação chave, a busca binária pode funcionar, mas para outros atributos como dados satélites, talvez não esteja ordenado. Página 2 de COM112 - Algoritmo e Estrutura de Dados II
Compartilhar