Ir para conteúdo

POWERED BY:

Arquivado

Este tópico foi arquivado e está fechado para novas respostas.

Pedro Sousa

Busca binária

Por , em C/C++

Recommended Posts

Pedro Sousa    0

Pedro Sousa
Postado

Olá amigos, esta é a minha 1ª mensagem no fórum, gostaria muito de ajuda, como resolver esta questão:"Construa uma página que faça uma busca binária de acordo com a descrição abaixo. Apágina deve conter uma caixa de texto longa, onde o usuário poderá definir um vetor denúmeros inteiros separados por virgulas. Em uma outra caixa de texto o usuário poderá digitarum número que será buscado no vetor pela busca binária. O código de uma pesquisa bináriaem um vetor de inteiros que devolve o índice onde se encontra um determinado elemento casoele exista ou o valor -1 caso ele não exista.Pesquisa binária: A pesquisa binária é feita apenas em estruturas ordenadas, uma vezque ela consiste numa busca parcelada. Na verdade, há três tipos de comparação:• compara-se o valor da chave com o valor contido no registro central; se igual,fim da pesquisa;• o valor da chave é menor que o valor do conteúdo do ponto central, e faz-seuma nova comparação com o valor central da primeira metade do arquivo;• o valor da chave é maior que o valor contido no ponto central, e faz-se novacomparação com o ponto central da segunda metade do arquivo.Para se obter o ponto central, utiliza-se a média simples (arredondando para baixo): PC= (I + N) / 2, onde I é a posição inicial e N o final. Por exemplo, considere o array (5, 7, 10,12, 22, 37, 49) e que estamos buscando o elemento 12.Primeiramente encontramos o ponto central, fazendo I = 1 e N = 6, temos PC = (1 + 6) /2 = 3, que é o elemento 10. Compara-se 12 com o PC, como não são iguais, calculamos umnovo valor central na metade posterior ao elemento 10, uma vez que o array está ordenado, esabemos que o valor 12, se existir, estará nesta metade. Então, I' = 3 e N' = 6, e PC' éaproximadamente 4, que é o elemento 12, é o que procurávamos"obrigado pela atenção.

Compartilhar este post

Link para o post
Compartilhar em outros sites
Ir para a lista de tópicos C/C++
×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.

  Aceito