1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Pesquisa binaria

Discussão em 'Programação' iniciada por nelo_inc, 7 de Maio de 2009. (Respostas: 2; Visualizações: 703)

  1. nelo_inc

    nelo_inc Power Member

    Boas pessoal... preciso de uma ajuda para melhorar este algoritmo da acordo com a pergunta seguinte...

    Altere o algoritmo de pesquisa binária de modo a que a pesquisa retorne a 1ª ocorrência do
    elemento a procurar. O método deve retornar a primeira posição do elemento ou -1 caso não esteja presente.

    A assinatura do método deverá ser:
    Código:
    public static int procuraBinariaPrimPosicao( Object v[], Object x )
     
    onde: v é o vector de elementos onde estão armazenados os elementos
    x é o elemento a procurar
    Código:
    public static int procuraBinariaPrimPosicao( String v[], String x ){
            int esq = 0;
            int dir = v.length - 1;
            int meio;
    
            while ( esq <= dir ) {
                meio = (esq + dir) / 2; 
                System.out.println("teste--->"+v[meio]);
                int cmp = ( v[meio]).compareTo(x);
                if ( cmp < 0 ) 
                    esq = meio + 1;
                 else if( cmp > 0 ) 
                    dir = meio - 1;
                 else return cmp;    
                
            }
                return -1;
            
        }
    
         
        public static void main(String[] args) {
    
            Dicionario dic = new Dicionario();
            long antes = System.currentTimeMillis();
    
    
            String [] dicionario = dic.getDicionario();
            for(int j = 0;j<dicionario.length;j++)
                //System.out.println(dicionario[j]);
    
                Arrays.sort(dicionario);
    
            //procuraBinariaPrimPosicao(dicionario,"curral");
    
    
            if(procuraBinariaPrimPosicao(dicionario,"zulu")==0)
                System.out.println("Encontrei");
            else
                System.out.println("Nao Encontrei");
    
            long depois = System.currentTimeMillis();
    
            System.out.println("Demorou "+(depois-antes)+" milisegundos");
    
        }
    
    }
     
    agradecia se pudessem que me dessem uma resposta com urgencia...

    fikem bem
     
    Última edição pelo moderador: 7 de Maio de 2009
  2. marcobjorge

    marcobjorge Power Member

    Parece-me que o codigo já faz o pedido na pergunta, o que queres melhorar exactamente?
     
  3. iznougud

    iznougud I quit My Job for Folding

    O código devolve 0 caso encontre e -1 caso não exista.
    Ele tem de editar o código para retornar a posição onde se encontra o valor encontrado.

    As alterações sao demasiado faceis... E esta thread não serve para resolver os problemas as pessoas mas a ensinar a resolver...


    O que tens de fazer é ir a funcao de pesquisa, descobrir onde é que ele encontra o valor pedido e em vez de devolveres 0 vais devolver o indice do array onde esta esse valor (é só trocar 1 palavra...)

    Depois tens de ir ao Main e alterar o modo como descobres se o valor existe ou nao, antes a funcao devolvia sempre 0 ou 1 e agora vai passar a devolver "qualquer coisa" ou -1

    O ideal e criares uma variavel para receber o resultado da funcao de pesquisa e depois analisar esse valor. Se for -1 é porque nao existe e se for outra coisa qualquer é porque existe e tens de mostrar ao utilizador em que posição e que a palavra esta.
     

Partilhar esta Página