5
import java.util.Arrays;

/**
 * @author Vinicius
 *
 */
public class Vetor04 {
    /**
     * @param args
     */
    public static void main(String[] args) {
        int vet[] = {3, 7, 6, 1, 9, 4, 5};
        int s = Arrays.binarySearch(vet, 3);
        System.out.println(s);

    }

}

Estou tentando fazer a o índice 3 do vetor vet aparecer mas ao invés de imprimir 1 imprime -5, qual o motivo disso acontecer?

2
  • Pesquisa binária tem o principio da ordenação ... acho que esse método segue isso.
    – novic
    11/01/2020 às 14:12
  • Todo conhecimento é válido, e você pode observar que as soluções podem caber dentro de um problema. Todas as experiências são válidas e respondi de acordo com a pergunta. Se a sua dúvida era sobre aquele método foi respondido e explicado de acordo com o seu questionamento e os motivos.
    – novic
    11/01/2020 às 17:07

2 Respostas 2

8

Embora você queira usar o método Arrays.binarySearch() para achar um valor em um array não classificado (o termo correto, porque ordenado o array está, ele tem uma ordem, a ordem de entrada de dados) e este método não deve ser aplicado. Ele foi criado para lidar quando você tem dados já classificados.

A solução de classificar o array para depois fazer a busca binária funciona, mas não está certo:

Fiat 147 todo detonado andando pelas ruas

Só vale a pena usar uma busca binária com uma coleção de dados que é garantidamente classificada já que o esforço de classificação é, no mínimo (e seria em uma condição ideal que na prática não acontece) igual a fazer uma busca linear, geralmente é bem maior. E na prática o algoritmo de classificação é menos eficiente até mesmo no detalhe que a busca linear na maioria das situações porque ela é ruim de localidade de referência. Pra ser mais preciso a busca linear chegar ser melhor até mesmo em arrays pequenos que já estão classificados.

Então se quer aprender aplicar o algoritmo de maneira correta não deve aplicar neste caso. Está aprendendo usar o mecanismo, mas também está aprendendo usá-lo da maneira incorreta e pode te perseguir pra sempre. E não estamos falando de pequena diferença quando os volumes são maiores, você poderá criar situações bem trágicas se continuar fazendo assim porque aprendeu que resolve no Stack Overflow.

Fazendo a busca linear produz o mesmo resultado de forma muito mais eficiente. Ainda que não precise dessa eficiência em um exercício o objetivo nem é este, é ensinar certo para aplicar bem nas próximas vezes:

class Main {
    public static void main (String[] args) {
        int vet[] = { 3, 7, 6, 1, 9, 4, 5 };
        for (int i = 0; i < vet.length; i++) if (vet[i] == 3) {System.out.println(i); break; }
    }
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

Tem várias outras formas de fazer isto.

E note que ele retorna a posição real, você pode querer isto ou não. A função pronto retorna a posição de inserção.

O pior caso deste algoritmo é O(N), mas pode ser O(1) no melhor caso. O melhor caso da busca binária que precisa classificar o dado é O(N)+O(1), mas na prática isto não acontece e a maioria dos casos será O(NlogN)+O(1) podendo até mesmo ser O(N2)+O(1). Em grandes volumes pode sair de segundos para horas.

Sem falar que assim não corre o risco do array não estar classificado e dar errado, como aconteceu. E a única forma de garantir em um código maior é:

  • classificar todas as vezes que for fazer a busca binária (muito ineficiente)
  • usar uma estrutura que você garante que foi classificada de início e não é mais mudada
  • usar uma estrutura que vai se classificando automaticamente toda vez que é mudada.

Pode não ser o que o AP quer, mas é importante para outras pessoas saberem o modo correto de fazer este tipo de coisa e não aprender errado. Note que isto está errado até mesmo neste caso proposto na pergunta, mesmo que funcione, a não ser que na pergunta estivesse escrito, a performance não importa e digitar menos caracteres importa.

Leia os comentários abaixo tem informações extras importantes.

18
  • 3
    Justamente que pelo que eu falei, não é eficiente. Você quer ir de SP ao Rio, mas não tem um carro, o que é melhor, pegar um ônibus ou comprar um carro só para isto? Ou olhando de outra forma, o que é melhor, ir a pé até lá ou fabricar um carro para poder ir? Muitos devem ter a impressão que um método simples de uma linha é algo bom, mas o que ocorre dentro dele é uma enormidade de processamento. Eu quis fazer em uma linha justamente porque as pessoas olham mais que uma e acham que é pior.
    – Maniero
    11/01/2020 às 16:35
  • 3
    @SDWQ12 simplificando: Arrays.binarySearch() é para ser usado quando o vetor já vai estar naturalmente ordenado pelo seu código. Se não está, é melhor usar outras soluções, e não binarySearch. A solução mais óbvia é o loop for (que é o que está aqui na resposta correta). Talvez a linguagem até já tenha um método de busca linear, que tende a ser melhor que a binária.
    – Bacco
    11/01/2020 às 16:52
  • 3
    @SDWQ12 é importante você entender o motivo, para tomar decisões corretas no futuro. Quando você recorre a um sort só para logo em seguida fazer search, demonstra desconhecimento de algoritmos e outras coisas fundamentais, pois só o sort sozinho já consome muito mais recursos do que um for (ele vai fazer geralmente mais de um for internamente e repassar pelos elementos mais de uma vez, pois trabalhará sobre todos e não somente no que você precisa). Recomendo estudara algoritmos de ordenação, e comparar as soluções.
    – Bacco
    11/01/2020 às 16:57
  • 4
    @SDWQ12 exemplo "real". Você tem 600 livros, misturados, e quer "O Processo" de Kafka. O for é você olhando um por um na sequência, e quando achar, pega e sai. Fim da história. O sort + binarySearch é você primeiro organizar TODOS 600 em ordem alfabética... e só depois que terminar de ordenar, começa a procurar. Pega o do meio, vê se é o que quer, se não for divide a pilha em dois, procura de um dos lados, e assim vai, até chegar no desejado (sendo que ao ordenar o livro já passou várias vezes na sua mão e vc nao pegou). Percebe que essa segunda alternativa não é muito inteligente?
    – Bacco
    11/01/2020 às 17:00
  • 3
    O que muitas vezes acontece é o programador não lembrar que quando ele faz um metodoDaLinguagem() a coisa não acontece magicamente. Isso está chamando um código que faz toda uma série de operações. É uma função cheia de código. Simplesmente ocorre que outro programador escreveu a função pra você e incluiu na linguagem, mas ela existe e a máquina vai ter que executar todos aqueles passos (independente do código ter vindo pronto e você não ter sido apresentado ao fonte dele, ou de um que você mesmo escreveu).
    – Bacco
    11/01/2020 às 17:20
4

Como eu relatei no comentário, a pesquisa binária tem o principio da ordenação crescente, e o seu array não está ordenado dessa forma do menor para o maior valor. Faça a ordenação com Arrays.sort que o local do valor é retornado, exemplo:

int vet[] = {3, 7, 6, 1, 9, 4, 5};
Arrays.sort(vet); // ordenação
int s = Arrays.binarySearch(vet, 3);
System.out.println(s);

Exemplo OnLine

Porque os números estranhos, segundo o livro da Kathy Sierra página 322, As buscas bem-sucedidas retornam o índice do elemento sendo procurado e Buscas mal-sucedidas retornam um índice int que representa o ponto de inserção.

Eu exemplifiquei sobre o código da pergunta, não podemos imaginar outra forma se na pergunta está descrito assim, claro (programação é sem limites) que pode ser feito de outra forma. As razões muitas vezes que levaram a esse questionamento é a explicação do texto anterior, ou seja, a falta de conhecimento sobre o que está fazendo.

Vale lembrar que aqui no site tem uma resposta praticamente igual Dificuldades com método binarySearch da Classe Arrays e foi citado a mesma solução.

Claro que poderia ter utilizado outros formas de pesquisas, como por exemplo Linear, mas, eu vou sempre pela pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .