Dúvida sobre Arrays.sort(arr1, elem1, COMPARATOR1) e Arrays.binarySearch(arr1, elem1, COMPARATOR2)

Pessoal,

Dado o código abaixo:

public static void main(String [] args) {
    	Integer[] a = {2,3,1,5};
    	
    	Comparator<Integer> comparator1 = new Comparator<Integer>(){
    		public int compare(Integer o1, Integer o2) {
    		return o2.compareTo(o1);
    	}};
    	
    	Comparator<Integer> comparator2 = new Comparator<Integer>(){
    		public int compare(Integer o1, Integer o2) {
    		return o1.compareTo(o2);
    	}};
    	
    	System.out.println("Array inicial: " + Arrays.asList(a));
    	
//Ordenei com um Comparator e pedi o índice informando outro Comparator, mas achou a posição.
    	Arrays.sort(a, comparator1);
    	List<Integer> listaOrdenada1 = Arrays.asList(a);
    	int posicao1 = Arrays.binarySearch(a, 3, comparator2); 
    	System.out.println("Com a ordenação 1, a lista fica assim " + listaOrdenada1 + " e a posição do número 3 é: " + posicao1);
    	
//Ordenei com um Comparator e pedi o índice informando outro Comparator, mas não achou a posição (como eu achei que fosse acontecer em ambas as versões.)
    	Arrays.sort(a, comparator2);
    	List<Integer> listaOrdenada2 = Arrays.asList(a);
    	int posicao2 = Arrays.binarySearch(a, 3, comparator1);
    	System.out.println("Com a ordenação 2, a lista fica assim " + listaOrdenada2 + " e a posição do número 3 é: " + posicao2);
    }

Alguém sabe explicar por que a saída é:

Array inicial: [2, 3, 1, 5]
Com a ordenação 1, a lista fica assim [5, 3, 2, 1] e a posição do número 3 é: 1
Com a ordenação 2, a lista fica assim [1, 2, 3, 5] e a posição do número 3 é: -1

[]'s

Na busca binária, primeiro, toma-se o elemento do meio e compara-se com o elemento chave de procura (no caso, o três). Se for igual, retorna a posição; se maior, toma-se o elemento do meio, entre o meio prévio e o final; se menor, toma-se o elemento do meio, entre o início e o prévio. E continua.

No caso do seu teste, no primeiro caso, temos:
meio = (inicio + fim)/2 = (0 + 3)/2 = 1
Por sorte, na primeira tentiva ele achou o 3 que você pediu. (Se você tentar um chave de procura que não esteja no meio do array ele não vai achar.)

No segundo caso, a chave de busca não é igual ao meio. O algoritmo compara para saber qual o proximo segmento a analisar. Pela ordenação, o elemento é maior do que o meio, mas o comparator é inverso, e vai informar que é menor. Como no primeiro segmento, a chave não está presente, retorna -1.

Perfeito, hadilson

testei procurando o elemento 1 (que não está no meio em nenhuma das ordenações) e o resultado foi:

Array inicial: [2, 3, 1, 5]
Com a ordenação 1, a lista fica assim [5, 3, 2, 1] e a posição do número 3 é: -1
Com a ordenação 2, a lista fica assim [1, 2, 3, 5] e a posição do número 3 é: -5

Esse sim é o resultado que eu esperava na versão anterior (2 resultados negativos).

Valeu!

GUJ Master Membro desde: 30/07/2007 22:43:05 Mensagens: 1151 Offline

Tentei compilar sua questão com todas as bibliotecas mas deu problema no List... pede pra mim renomear ele...

Notícias, artigos e o maior fórum brasileiro sobre Java