Métodos de Pesquisa

Pesquisa SequencialÉ o tipo de busca mais simplesA partir do primeiro registro, pesquisa sequencialmente até encontrar a chave procuradaNão requer ordenação dos elementosPesquisa sequencialmente do primeiro até o último registro. Quando encontrar a chave desejada, para.Código: Funcao Buscar (x, n: inteiro) : inteirovar resp, i: inteiroinicio resp <- -1 para i de 1 ate n faca se (v[i] = x) entao resp <-i //chave encontrada fimse fimpara retorne respfimfuncao

Pesquisa Sequencial: SentinelaUma maneira de tornar o algoritmo mais efciente é usar um sentinela:Sentinela: consiste em adicionar um elemento de valor x no fnal da tabelaO sentinela garante que o elemento procurado será encontrado, o que elimina uma expressão condicional, melhorando a performance do algoritmo Código:Função Buscar (x, n: inteiro) : inteiroVar i:inteiroInicio i <- 1 v[n+1] <- x Enquanto (x<> v[i]) faça i<- i+1 fmenquanto se (i<=n) entao retorne i //chave encontrada senao retorne -1 //chave não encontrada fimsefimfuncao

Pesquisa BináriaDivide o vetor em duas partesVerifica em qual das partes o item com a chave se localizaRealiza sucessivas divisões do vetor e compara o elemento buscado (chave) com o elemento no meio do segmentoSe igual, a busca termina com sucessoSe o elemento do meio for menor que o elemento buscado, então a busca continua na metade posterior do vetorSe o elemento do meio for maior que a chave, a busca continua na metade anterior do vetor Código: Funcao BuscaBinaria (x, n:inteiro) : inteirovarretorna, min, max, meio: inteiroinicioretorna <- -1min <- 1max <- nenquanto (min <= max) facameio <- (min + max) \ 2se (vetor[meio] = x) entaoretorna <- meio //chave encontradainterrompasenaose (vetor[meio] < x) entaomin <- meio + 1senaomax <- meio - 1fimsefimsefimenquantoretorne retornafimfuncao