Baixe o app para aproveitar ainda mais
Prévia do material em texto
Busca em vetor Algoritmos I Prof. Thiago Meirelles Ventura UFMT – IC – 2013/1 Introdução O vetor é uma forma de armazenar valores É de grande importância localizar determinados elementos dentro de um vetor Por isso existem as buscas em vetores Busca linear simples Compara o elemento com cada item do vetor até encontrar o respectivo item Busca linear simples 56 -34 1345 0 -371 0 Busca linear simples 56 -34 1345 0 -371 0 Busca linear simples 56 -34 1345 0 -371 0 Busca linear simples 56 -34 1345 0 -371 0 Busca linear simples 56 -34 1345 0 -371 0 Exercício 1 Faça um algoritmo que leia um numero inteiro n entre 1 e 100 Leia n valores reais em um vetor Leia um valor x Escreva na saída a primeira posição do vetor onde x aparece, ou zero caso não apareça. Exercício 1 Resolver da maneira simples Tentar otimizar Busca sequencial com sentinela Está sendo feita uma comparação apenas para verificar se o laço chegou ao fim por encontrar o elemento ou por chegar ao fim do vetor. E se tivermos certeza que o elemento sempre será encontrado? Como podemos fazer isso? Podemos inserir o elemento a ser encontrado no final do vetor (sentinela) Busca binária E se o vetor possuir milhões de elementos? Quanto tempo levará a busca? Busca binária A maneiras mais eficazes de efetuar as buscas. Uma delas é aproveitar da estratégia "dividir para conquistar” A busca binária utiliza essa estratégia Busca binária Requisito: O vetor deve estar ordenado Procedimento: O elemento buscado é comparado ao elemento do meio do vetor Se igual, encontrou o elemento desejado Se menor, busca-se na metade inferior do vetor Se maior, busca-se na metade superior do vetor Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Busca binária Busca-se por 142 -147 -34 5 98 142 0 32 99 964 Exercício 2 Faça um algoritmo que leia um numero inteiro n entre 1 e 100 Leia n valores reais em um vetor Assegura-se que o vetor será preenchido de maneira ordenada de forma crescente Leia um valor x e escreva na saída a posição no vetor onde x aparece, ou zero caso não apareça Utilize a busca binária. Exercício 3 Faça um algoritmo que leia um vetor de até 500 elementos Diga se ele está ordenado de forma ascendente e se os valores são todos distintos entre si Em caso positivo, peça que ele digite ainda um valor x e diga em que posição do vetor ele aparece, utilizando uma técnica que tire vantagem da característica ordenada do vetor.
Compartilhar