Duvida binarySearch()

Programação Java
#1

Ola pessoal,

acabei de ler o capitulo sobre Collections e Generics e parece que entendi boa parte, mas uma coisa que quando fui testar nao deu o resultado que eu esperava eh o tal do metodo binarySearch… os resultados nao foram conforme eu esperava, pelo que eu sei ele deve retornar a posicao que o valor esta no array. acho que nao entendi nada disso, alguem pode me explicar? esse codigo ai eh um teste que eu fiz pra testar soh que os resultados nao sao conforme eu esperava que fosse…

[code] import java.util.*;

public class Test
{
public static void main(String[] args)
{
String[] s ={“map”,“jeep”,“vec”,“ka”};

    System.out.println(Arrays.binarySearch(s,"map"));
}

} [/code]

como podem ver, quando eu executei este codigo pesquisando por “map” no array, ele me retorna -3… mas nao era pra retornar a posicao? no caso 0??? e quando eu coloco pra pesquisar o “jeep” beleza, retorna a posicao 1… com “vec” tambem, tudo certinho retorna a posicao 2… agora com “ka” retorna -3 tambem… o que que acontece? qualquer ajuda pra clarear minha mente eh muito bem vinda.

Obrigado.

#2

Um pré-requisito para a busca binária é que o array esteja ordenado.

#3

Legal… isso ja foi uma luz…

 public class Test
{    
    public static void main(String[] args)    
    {    
       String[] s ={"a","c","d"};      
  
       System.out.println(Arrays.binarySearch(s,"e"));  
    }    
}

vendo outros posts eu percebi que caso ele nao ache o que foi solicitado ele insere um valor negativo da posicao que ele deveria estar… neste meu outro exemplo ele retorna -4 nao deveria ser -3 ???

#4

gumatias,

acontece que o 0 é um valor válido de índice.

por exemplo:

String[] s = {a,c} System.out.print(s[0]) + " " +System.out.print(s[1]);

e teríamos a saída a c.

Se tu adicionasse o “b”, pela ordem natural, ele deveria ser adicionado no s[1], não é verdade?
Então, como o 0 é um valor válido de índice, s[1] é a segunda posição.
Logo, o retorno do binarySearch nesse caso seria -2.

Espero ter ajudado.
Abraço

#5

olá,

Caso seja encontrado a resposta, ele informará o indice.

Caso contrário, ele informará seguindo essa pequena fórmula: (-(ponto de inserção) -1).

entaum de modo correto ele t apresentou o indice -4 e naum -3.

Ricardo

#6

ahhhh… agora entendi hehe…
brigadao!!

#7

Ah, outra coisa, já ia me esquecendo.
A classe String implementa Comparable, para que o sort funcione. O Comparable classifica Strings em ordem natural, ou seja, em ordem alfabética.

Os dados do teu array são:
a, c, d.

O retorno do e é -4 porque em ordem alfabética ainda falta o b no teu array!

Abraço

#8

[quote=L.Bach]Ah, outra coisa, já ia me esquecendo.
A classe String implementa Comparable, para que o sort funcione. O Comparable classifica Strings em ordem natural, ou seja, em ordem alfabética.

Os dados do teu array são:
a, c, d.

O retorno do e é -4 porque em ordem alfabética ainda falta o b no teu array!

Abraço[/quote]

bom, eu peguei o exemplo dado e fiz diversas modificações no array e sempre retornou -4.
Desculpa, mas eu não acredito que ele retornou -4 pelo fato do caracter ‘b’ estar ausentado !!!
E sim que a próxima posição disponível seria a terceira (based-zero).

Ricardo

#9

Tem toda razão, Ricardo.
Falha minha.

Valeu.

#10

Ah… legal ricardo13 e L.Bach agora eu entendi esse bem dito metodo perfeitamente…
:lol:

#11

ve se este codigo lhe ajuda um pouco, pelo que tenho lido e entendido sobre a binarySearch(), sempre temos que usar o Arrays.sort() no array que devemos procurar.

logo após utilizar o método sort() , tdo funciona bem.

import java.util.*;

public class D5 {

    public D5() {
    }
    

    public static void main(String[] args)    
    {    
        String[] s ={"map","jeep","vec","ka"};    
        
        System.out.print("Não ordenado: ");
        for(String sAux : s)
        	System.out.print(sAux + " ");
        	
        System.out.println("\nRetorno Busca (map): " + Arrays.binarySearch(s,"map"));
        System.out.println("Retorno Busca (jeep): " + Arrays.binarySearch(s,"jeep"));
        System.out.println("Retorno Busca (vec): " + Arrays.binarySearch(s,"vec"));
        System.out.println("Retorno Busca (ka): " + Arrays.binarySearch(s,"ka"));
        	
        Arrays.sort(s);
        
        System.out.print("\nOrdenado: ");
        for(String sAux : s)
        	System.out.print(sAux + " ");
        	
        System.out.println("\nRetorno Busca Ordenada (map): " + Arrays.binarySearch(s,"map"));
        System.out.println("Retorno Busca Ordenada (jeep): " + Arrays.binarySearch(s,"jeep"));
        System.out.println("Retorno Busca Ordenada (vec): " + Arrays.binarySearch(s,"vec"));
        System.out.println("Retorno Busca Ordenada (ka): " + Arrays.binarySearch(s,"ka"));
    }        
    
}

Abraço a todos.

#12