Document

Esse método se chama de busca binária porque a cada iteração dividimos o conjunto em dois subconjuntos, até que chegamos a um conjunto com apenas um elemento. Matematicamente podemos escrever que a quantidade de iterações necessárias para buscar um valor usando o método binário é:

k=log₂N

Vamos considerar uma lista com 1024 elementos. Se usássemos o algoritmo de pesquisa linear teríamos que realizar 1024 comparações. Se utilizarmos o método binário, então teremos:

k=log₂1024=10

Esse método então melhoraria a eficiência da busca em mais de cem vezes. Vamos agora ver um exemplo de implementação do método de busca binária.

Exemplo 1_3_2: exemplo de busca binária.

public class BuscaBinária {

    
    private static final int NOT_FOUND = -1;
    public static void main(String[] args) {

        int[] valores = {1,2,7,15,35,41,42,48,49,50,51,58,59,60,63,65};
        int retorno = BuscaBinaria(valores,60);
        System.out.println("indice final: "+ retorno);
    }
    public static  int BuscaBinaria(int[] valores, int valorprocurado){
        int inferior, superior,media;
        
        inferior=0;
        superior = valores.length-1;
        media = (inferior+superior)/2;
        System.out.println("inferior|-------media -------|superior");
        System.out.println("   "+inferior+"\t|-------  "+media+"   -------|"+superior);
        while(inferior<=superior && valores[media]!=valorprocurado){
            
            if(valores[media]<valorprocurado){
                inferior=media-1;
            }
            else{
                superior=media-1;
            }
            media = (inferior+superior)/2;
            System.out.println("   "+inferior+"\t|-------  "+media+"  -------|"+superior);
        }
        if(inferior>superior){
            media=-1;
        }   
        return media;
    }
}

O resultado da execução desse programa será o seguinte:

Inferior|-------media -------|superior
0         |-------   7     -------|15
6         |-------   10   -------|15
9         |-------   12   -------|15
11       |-------  13    -------|15
índice final: 13

Podemos verificar no resultado que o limite inferior vai sendo alterado até que o valor que ocupa a posição definida pela média se torna igual ao valor procurador.