3

Partindo do principio que a busca binária funciona apenas com vetor de inteiros ordenados, caso eu tenha que buscar um inteiro em um vetor ordenado a velocidade da busca seria muito mais rápido do que uma busca sequencial, mas minha duvida é, se meu vetor não estiver ordenado quanto influenciaria na velocidade em relação a busca sequencial caso eu tenha que ordená-lo? e se pudermos ir mais a fundo pense em uma busca binária em um vetor de String o processo seria:

  1. Converter cada item do vetor em um numero decimal
  2. Ordenar o vetor
  3. Realizar a busca binária

Nesses dois exemplos quanto influenciaria na velocidade em relação a busca sequencial os processos antes da busca binaria?

1
  • Depende da quantidade de buscas que irá realizar após a ordenação. Se forem poucas pesquisas não vale a pena.
    – user4552
    26/03/2014 às 17:33

3 Respostas 3

4

se meu vetor não estiver ordenado quanto influenciaria na velocidade em relação a busca sequencial caso eu tenha que ordená-lo?

Se você tiver que ordenar um vetor para depois fazer uma busca com certeza o processo será mais lento, só compensará ordenar se você tiver que fazer várias buscas.

uma busca binaria em um vetor de String

A classe String (em Java) implementa a interface Comparable o que permite que se use o método binarySearch() diretamente sobre seu vetor de Strings, sem a necessidade de transformar em inteiros (seja lá como você planeja fazer isso).

Ou seja, você pode ordenar o vetor simplesmente fazendo assim:

String[] sa = {"um", "dois", "tres", "quatro"};
Arrays.sort(sa);
System.out.println(Arrays.binarySearch(sa, "um")); //imprime "3" que é a posição do
                                                   //elemento "um" no vetor ordenado

quanto influenciaria na velocidade em relação a busca sequencial os processos antes da busca binaria?

Depende do tamanho do seu vetor e de quantas vezes você fará uma busca nele depois de ordenado.

Apenas saiba que o método sort() tem complexidade O(n log(n)).

Referências:

método Arrays.sort() - Java SE7

Classe String - Java SE7

Interface Comparable - Java SE7

4
  • Muito obrigado @Math sua resposta foi bastante construtiva , como faço uma busca binária em um vetor de strings sem precisar converte-los para inteiro como faz a classe String do Java? 28/03/2014 às 22:58
  • Não entendi bem sua pergunta. O código que eu pus na resposta faz exatamente isso, com o Arrays.sort() e Arrays.binarySearch(). Se não for isso, poderia esclarecer qual sua dúvida?
    – Math
    29/03/2014 às 11:54
  • Minha dúvida é sobre o funcionamento interno do método binarySearch, na sua resposta você disse que ele faz a Busca binária sem precisar converter para inteiros, como ele faz isso? 29/03/2014 às 15:13
  • Toda classe que deseja ser ordenada deve implementar a interface Comparable e sobrescrever o metodo compareTo(). A classe String faz this.charAt(k)-anotherString.charAt(k) para dizer qual String está antes de outra quando ordenadas, esse código quer dizer que a comparação de duas Strings é o resultado da comparação baseado no valor Unicode de caracter a caracter de cada uma delas. Veja o compareTo() da String.
    – Math
    30/03/2014 às 18:34
3

As eficiências seriam:

  • n.log(n) para ordenar
  • log(n) para buscar quando ordenado binarysearch
  • n para buscar desordenado

Vamos dizer que a gente tenha 10K elementos

Para ordenar e buscar:

10K.log(10K)+log(10K) = 44K de eficiência

Para apenar buscar desordenado seriam apenas:

10K = 10k eficiência

A busca desordenada é mais rápida do que ordenar e buscar. O problema de ordenar a lista é que seu custo é muito alto. Então nunca seria mais eficiente ordenar antes de buscar para apenas 1 unica busca.

Se tivesse que fazer mais busca ai o custo desta ordenação inicial sumiria.

Por exemplo para esta busca, se fosse feito 10 vezes teríamos:

Ordenado: 44+40 = 88
Desordenado: 10*10 = 100

Lembrando que a eficiência O(1) é a mais eficiente, então 88 é melhor que 100.

3

Bom, a velocidade com que os processos necessários para tornar a busca binária viável são realizados está diretamente associada ao número de vezes que os mesmos são executados.

No caso, se o vetor não estiver ordenado e você não souber uma "pista" sobre um jeito de ordená-lo de uma maneira mais rápida e eficaz (baseando-se nos próprios valores do vetor), uma busca sequencial será sempre a melhor alternativa.

Em suma, só é interessante fazer uma busca binária ao invés da sequencial quando:

  1. O vetor em questão é ordenado (como já apontado em sua pergunta);
  2. O número de tarefas realizadas para ordenar um vetor a partir de um algoritmo já conhecido é menor do que o número de comparações de valor por valor.

Pense na seguinte situação (usarei C# para demonstrar):

  • Você deseja buscar por um número (38 por exemplo) dentro de um vetor com 40 posições que não está ordenado:

    int valorDesejado = 38;
    int[] vetor = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
                      22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 39};
    

    Você tem uma pista ou, nesse caso, sabe explicitamente que seu vetor tem os dois últimos valores invertidos.

  • Comparando os dois tipos de buscas (considerando gasto de processamento em operações de soma, divisão, disjunção e comparação de maneira equivalente), na sequencial você realizaria 38 testes de comparação (tirando a comparação do próprio laço) e faria o incremento de sua variável contadora i o mesmo número de vezes:

    for (int i = 0; i < vetor.Length; i++)
        if (valorDesejado == vetor[i])
            Console.WriteLine("Valor encontrado na posicao " + i);
    
    /* Total:
     * 38 Operações
     * 38 Comparações
     */
    

    Por outro lado, antes de realizar a busca binária, você só precisa de três operações para trocar os valores de posição (para isso usarei o algoritmo XOR de troca), somando ao total duas operações e uma comparação por ciclo:

    // Usando XOR Swap: 3 operações
    vetor[38] ^= vetor[39];
    vetor[39] ^= vetor[38];
    vetor[38] ^= vetor[39];
    
    // Busca binária
    int esq, meio, dir;
    esq = -1;
    dir = vetor.Length;
    
    while (esq < dir - 1) // Para buscar pelo 38, o ciclo só se repetirá 6 vezes
    {
        meio = (esq + dir) / 2; // Duas operações (soma e divisão)
        if (vetor[meio] < valorDesejado) // Uma comparação
            esq = meio;
        else
            dir = meio;
    }
    Console.WriteLine("Valor encontrado" + dir);
    
    /* Total:
     * 6 * 2 + 3 = 15 Operações
     * 6 * 1 = 6 Comparações
     */
    

Você deve fazer log-in para responder a esta pergunta.

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