Ir para o conteúdo
Thorondor

Pesquisa binária com ciclo For

Mensagens Recomendadas

Thorondor    0
Thorondor

Oi pessoal, estou programando em MATLAB, mais propriamente num Bloco da System generator que usa MATLAB, mas as funções são limitadas, e queria fazer uma pesquisa binária de um vector, com as seguintes condicionantes impostas pelo próprio bloco:

- Apenas posso usar fors e ifs;

- No ciclo for, a variavel que é incrementada (por exemplo o i de "for i=1:x", não pode ser mudada dentro do ciclo;

- Apenas posso dividir por números de base 2;

- Existem mais, mas não m lembro de mais nenhuma relevante.

Obrigado desde já pela vossa atenção e tempo.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Eu nunca trabalhei com matlab, mas posso tentar ajudar com a lógica.

Suponho que saibas o que é uma pesquisa binária?

Não podes ter outra variável além da variável do ciclo e poder interromper o ciclo quando terminas a pesquisa? É que só com uma variável incrementada 1 a 1, não creio que se possa fazer uma pesquisa binária.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Continuo sem saber se sabes como se faz uma pesquisa binária, é que se sim, o que vou dizer não deve servir de nada pois não podes implementar devido às restrições a que estás sujeito.

Assumindo que tens um vector V com N elementos já ordenados de forma crescente e pretendes saber se um valor X se encontra no vector, são necessárias mais 3 variáveis: left , right e mid.

Não sei se os indices começam em 0 ou 1, assumindo que começam em 0:

left = 0 , right = N-1;

for i=1:N  // não podem existir N iterações na pesquisa binária, é apenas para termos um ciclo
     mid = (left + right) / 2 ; // 2 é potência de 2, não tens problema
     if ( V[mid] < X )
             right = mid-1 ;  // resposta encontra-se no intervalo [ left , mid [
     else if ( V[mid] > X )
             left = mid+1 ;  // resposta encontra-se no intervalo ] mid , right ]
     else 
             quebra o ciclo pois encontramos o valor na posição mid

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Thorondor    0
Thorondor

O problema disso é que o mid vai acabar por ter um valor decimal, e não consegues obter uma célula dum vector com casa decimal

Por isso tenho de verificar se o mid é par ou impar pelo caminho, e não tenho nenhuma função especifica para isso :S

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Thorondor    0
Thorondor

Agora o problema reside em descobrir qts vezes eu tenho d correr o ciclo, d maneira a conseguir poupar o máximo instruções :S

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Eu pensei que tinhas a divisao inteira disponivel, daí não haver problemas com casas decimais.

O ciclo corre em O( log N ). O ideal era parar o ciclo como eu disse, não podes fazer isso em matlab? É que senão vais estar quase sempre a fazer iterações a mais..

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade