Arrays.binarySearch?

a busca binária é uma busca otimizada em comparação com a busca linear… Só que o array tem que estar ordenado. A busca binária funciona assim:
você testa se o valor que você está procurando é maior ou menor do que a metade do valor. Se for maior ele procura na 2a parte, subdividindo o problema nesse mesmo eskema, até achar o valor; então o método retorna o índice em que esse elmento está, ou o ponto de inserção do elemento, caso o elemento não se encontre no array.
para saber mais:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html#binarySearch(int[],%20int).

Por favor me ajudem nisso…

Não estou conseguindo entender muito bem,

Tenho as seguintes situações:

1.Esse exemplo abaixo a saída é 2 -1 pelo que entendi ele achou o champion na posição 2 e o “You” ele não encontrou e colocou -1

package collections;

import java.util.Arrays;

public class TesteBinarySearch2{
      public static void main(String[] args) {
		
		String[] arr = { "java", "champ", "champion" };
		System.out.print(Arrays.binarySearch(arr, "champion"));
		System.out.print(Arrays.binarySearch(arr, "You"));
		
	}
                                      
}

Agora nesse abaixo, não entendi porque a String “java” ele não mostrou a posição dele se é exatamente igual a que está no vetor:
A saída foi -3 -1

package collections;

import java.util.Arrays;

public class TesteBinarySearch3 {
	public static void main(String[] args) {

		String[] arr = { "java", "champ", "you" };
		
		System.out.print(Arrays.binarySearch(arr, "java"));
		System.out.print(Arrays.binarySearch(arr, "You"));

	}

}

brunoprogramadorjava,

Não funcionou no segundo exemplo porque o array arr não está ordenado. Se você chamar Arrays.sort(arr); antes de chamar Arrays.binarySearch(), deverá localizar os elementos corretamente.

al.barbosa,

Primeiramente, agradeço pela ajuda e realmente depois que ordenei o segundo funcionou…

mas fiquei com uma dúvida: - Qual ordenação que o primeiro exemplo seguiu???

porque crescente e decrescente não é… e quando coloco o sort a saída muda de 2 para 1 no primeiro print do primeiro exemplo ou seja mesmo não estando

ordenado ele identifica na posição “champion” na posicao 2 sendo que o segundo exemplo não identifica o “java”, mas ordenando identifica normal…

Todos os exemplos estão errados (estão com dados de entrada desordenados).

Quando você aplica um algoritmo com dados errados, pode ser que ele gere uma resposta “errada” ou uma resposta “certa” - isso pode ser sorte ou azar.

Calhou de dar uma resposta “certa” no primeiro exemplo, mas como você percebeu, foi só sorte.

Muito obrigado a todos…

entendi, so que em uma questão do exame que pedir para mostrar a saída fica complicado quando não tem o sort então,

onde estou fazendo os simulados é no www.javachamp.com e a parte que vi que estou perdendo mais pontos é em coleções,

por isso que estou reforçando antes de fazer o exame, mas agradeço a todos…

entanglement:

Todos os exemplos estão errados (estão com dados de entrada desordenados).

Quando você aplica um algoritmo com dados errados, pode ser que ele gere uma resposta “errada” ou uma resposta “certa” - isso pode ser sorte ou azar.

Calhou de dar uma resposta “certa” no primeiro exemplo, mas como você percebeu, foi só sorte.

Exatamente.

olá pessoal eu iniciante em java e aproveitando o tópico do amigo ae preciso de uma ajudinha de vcs…

int [] a ={32,45,89,66,12,35,10,96,38,15,13,11,65,81,35,64,16,89,54,19};
System.out.println(Arrays.binarySearch(a, 10));

eu estou querendo que ele me retorne o índice do elemento 10, mas toda vez que rodo o programa
ele me retorna -1 pq isso tá acontecendo?

agradeço desde já!!!

romariowd:

olá pessoal eu iniciante em java e aproveitando o tópico do amigo ae preciso de uma ajudinha de vcs…

int [] a ={32,45,89,66,12,35,10,96,38,15,13,11,65,81,35,64,16,89,54,19};
System.out.println(Arrays.binarySearch(a, 10));

eu estou querendo que ele me retorne o índice do elemento 10, mas toda vez que rodo o programa
ele me retorna -1 pq isso tá acontecendo?

agradeço desde já!!!

A busca binária parte do princípio que o seu vetor esteja ordenado em ordem crescente, assim a cada pesquisa realizada ele divide ao meio o tamanho do escopo
da pesquisa, se o número que está no meio for maior ou menor que o número procurado ele divide novamente para parte de cima do vetor onde supostamente estão os maiores números ou para baixo onde supostamente estão os números menores, no seu caso você pode ver que este vetor não está ordenado em ordem crescente, por isso é retornado o valor -1, que nesse caso significa que não existe o número procurado.

Valeu C.porto
Muito Obrigado!!!

Segundo o livro da Kathy Sierra página 322.

Depois que li esse pedaço, que fui entender o porque de gerar aqueles números estranhos quando não estava ordenado…

As buscas bem-sucedidas retornam o índice do elemento sendo procurado.

Buscas mal-sucedidas retornam um índice int que representa o ponto de inserção. O ponto de inserção é o lugar no conjunto/array onde o elemento seria inserido para manter o conjunto / array corretamente classificado. Pelo fato de valores de retorno positivos e 0 indicarem buscas bem-sucedidas, o método binarySearch() usa números negativos para indicar pontos de inserção. Uma vez que 0 é um resultado válido para uma busca bem-sucedida, o primeiro ponto de inserção. Uma vez que 0 é um resultado válido para uma busca bem-sucedida , o primeiro ponto de inserção disponível é -1. Assim o ponto de inserção é realmente representadoo com (-(ponto de inserção - 1) .Por exemplo, se o ponto de inserção de uma busca estiver no elemento 2, a valor real do ponto retornado será -3.

A coleção/array onde está sendo feita a busca deve ser classificado antes que você possa procurar por nele.

Se você tentar procurar em um array ou coleção que ainda não foi classificado, os resultados da busca não serão previsíveis.

Se a coleção/array em que você deseja procurar tiver sido classificado na ordem natural, a busca deve ser feita nessa mesma ordem. (Isso é feito ao NÃO se enviar um Comparator como argumento para o método binararySearch(). )

Se a coleção /array em que você deseja procurar tiver sido classificado com um Comparator, a busca deve ser feita usando-se o mesmo o Comparator, que é passado como o segundo argumento ao método binarySearch(). Lembre-se de que Comparators não podem ser usados ao se buscar em arrays de tipos primitivos.