Algoritmo de pesquisa binária com EXEMPLO

Antes de aprendermos a busca binária, vamos aprender o que é uma busca.

O que é pesquisa?

Pesquisa é um utilitário que permite ao usuário encontrar documentos, arquivos, mídia ou qualquer outro tipo de dado contido em um banco de dados. A pesquisa funciona com base no simples princípio de combinar os critérios com os registros e exibi-los ao usuário. Desta forma, funciona a função de pesquisa mais básica.

O que é Pesquisa Binária?

A busca binária é um tipo avançado de algoritmo de busca que encontra e recupera dados de uma lista ordenada de itens. Seu princípio básico de funcionamento envolve dividir os dados da lista ao meio até que o valor desejado seja localizado e exibido ao usuário no resultado da busca. A busca binária é comumente conhecida como... pesquisa de meio intervalo pesquisa logarítmica.

Como funciona a pesquisa binária?

A pesquisa binária funciona da seguinte maneira:

• O processo de busca inicia-se localizando o elemento do meio na matriz de dados ordenada.
• Em seguida, o valor da chave é comparado com o elemento.
• Se o valor da chave for menor que o elemento do meio, a pesquisa analisa os valores superiores ao elemento do meio para comparação e correspondência.
• Caso o valor da chave seja maior que o elemento do meio, a pesquisa analisa os valores inferiores ao elemento do meio para comparação e correspondência.

Algoritmo de Busca Binária (Pseudocódigo)

A busca binária pode ser escrita como uma rotina iterativa curta. Ela mantém dois ponteiros, baixo e alto, e restringe o intervalo até que o alvo seja encontrado ou o intervalo fique vazio.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

A rotina retorna o índice do alvo em caso de sucesso e -1 quando o valor não está presente. Como o intervalo é reduzido pela metade a cada iteração, o loop é executado no máximo log₂(n) vezes.

Exemplo de pesquisa binária

Vejamos o exemplo de um dicionário. Se você precisar encontrar uma determinada palavra, ninguém percorre cada palavra de maneira sequencial, mas localiza aleatoriamente as palavras mais próximas para pesquisar a palavra desejada.

A imagem acima ilustra o seguinte:

1. Você tem uma matriz de 10 dígitos e o elemento 59 precisa ser encontrado.
2. Todos os elementos são marcados com índices de 0 a 9. Agora, calcula-se o ponto médio do array. Para isso, pegam-se os valores mais à esquerda e mais à direita do índice e dividem-se por 2. O resultado é 4.5, mas arredondamos para baixo. Portanto, o ponto médio é 4.
3. O algoritmo remove todos os elementos do meio (4) até o limite inferior, porque 59 é maior que 24, e agora o array fica com apenas 5 elementos.
4. Agora, 59 é maior que 45 e menor que 63. O valor do meio é 7. Portanto, o valor do índice da direita passa a ser o valor do meio menos 1, que é igual a 6, e o valor do índice da esquerda permanece o mesmo de antes, que é 5.
5. Neste ponto, você sabe que 59 vem depois de 45. Conseqüentemente, o índice esquerdo, que é 5, também fica no meio.
6. Essas iterações continuam até que o array seja reduzido a apenas um elemento ou o item a ser encontrado se torne o meio do array.

Exemplo 2

Vejamos o exemplo a seguir para entender como funciona a busca binária.

1. Você tem uma matriz de valores classificados variando de 2 a 20 e precisa localizar 18.
2. A média dos limites inferior e superior é (l + r) / 2 = 4. O valor que está sendo procurado é maior que o ponto médio, que é 4.
3. Os valores da matriz menores que o valor médio são descartados da pesquisa, e os valores maiores que o valor médio 4 são pesquisados.
4. Este é um processo de divisão recorrente até que o item real a ser pesquisado seja encontrado.

Por que precisamos da pesquisa binária?

Os seguintes motivos fazem da busca binária a melhor escolha para ser usada como algoritmo de busca:

• A busca binária funciona de forma eficiente em dados ordenados, independentemente do tamanho dos dados.
• Em vez de realizar a pesquisa percorrendo os dados em sequência, o algoritmo binário acessa aleatoriamente os dados para encontrar o elemento necessário. Isso torna os ciclos de pesquisa mais curtos e precisos.
• A busca binária realiza comparações dos dados ordenados com base em um princípio de ordenação, em vez de usar comparações de igualdade, que são mais lentas e geralmente imprecisas.
• Após cada ciclo de busca, o algoritmo divide o tamanho da matriz pela metade; portanto, na próxima iteração, ele trabalhará apenas na metade restante da matriz.

Aprenda mais em nosso próximo tutorial sobre Pesquisa Linear: Python, C++ Exemplo.

Busca binária versus busca linear

A busca binária e a busca linear são as duas maneiras mais comuns de encontrar um valor em uma coleção. A tabela abaixo destaca as diferenças entre elas:

Resumindo, a busca binária é muito mais rápida em grandes conjuntos de dados ordenados, enquanto a busca linear é mais simples e a única opção quando os dados não estão ordenados.

Perguntas Frequentes