Algoritmo de pesquisa binária com EXEMPLO

Antes de aprendermos a pesquisa binária, vamos aprender:

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?

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

Como funciona a pesquisa binária?

A pesquisa binária funciona da seguinte maneira:

• O processo de pesquisa inicia localizando o elemento intermediário da matriz classificada de dados
• Depois disso, 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 do 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 mais baixos do elemento do meio para comparação e correspondência

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 o índice de 0 a 9. Agora, o meio do array é calculado. Para fazer isso, você pega os valores mais à esquerda e à direita do índice e os divide por 2. O resultado é 4.5, mas pegamos o valor mínimo. Portanto, o meio é 4.
3. O algoritmo descarta todos os elementos do meio (4) para 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. Conseqüentemente, o valor do índice direito se torna o meio – 1, que é igual a 6, e o valor do índice esquerdo 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 o funcionamento da pesquisa 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 pesquisado é maior que o médio que é 4.
3. Os valores da matriz menores que o meio são eliminados 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 tornam a pesquisa binária uma escolha melhor para ser usada como algoritmo de pesquisa:

• A pesquisa binária funciona de forma eficiente em dados classificados, 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 pesquisa binária realiza comparações dos dados classificados com base em um princípio de ordenação, em vez de comparações de igualdade, que são mais lentas e, em sua maioria, imprecisas.
• Após cada ciclo de pesquisa, o algoritmo divide o tamanho do array pela metade, portanto na próxima iteração funcionará apenas na metade restante do array

Aprenda nosso próximo tutorial de Pesquisa Linear: Python, C++ Exemplo

Resumo

• Pesquisa é um utilitário que permite ao usuário pesquisar documentos, arquivos e outros tipos de dados. Uma pesquisa binária é um tipo avançado de algoritmo de pesquisa que encontra e busca dados de uma lista classificada de itens.
• A pesquisa binária é comumente conhecida como pesquisa de meio intervalo ou pesquisa logarítmica
• Ele funciona dividindo o array pela metade em cada iteração abaixo do elemento necessário.
• A algoritmo binário ocupa o meio da matriz dividindo a soma dos valores dos índices mais à esquerda e à direita por 2. Agora, o algoritmo elimina o limite inferior ou superior dos elementos do meio da matriz, dependendo do elemento a ser encontrado.
• O algoritmo acessa aleatoriamente os dados para encontrar o elemento necessário. Isso torna os ciclos de pesquisa mais curtos e precisos.
• A pesquisa binária realiza comparações dos dados classificados com base em um princípio de ordenação, em vez de usar comparações de igualdade que são lentas e imprecisas.
• Uma pesquisa binária não é adequada para dados não classificados.