Antes de aprendermos a pesquisa binária, vamos aprender:
O que é pesquisa?
A pesquisa é um utilitário que permite ao usuário encontrar documentos, arquivos, mídia ou qualquer outro tipo de dado mantido em um banco de dados. A pesquisa funciona com o princípio simples de combinar os critérios com os registros e exibi-los ao usuário. Desta forma, a função de pesquisa mais básica funciona.
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 de funcionamento principal envolve dividir os dados na lista pela metade até que o valor necessário seja localizado e exibido para o usuário no resultado da pesquisa. A pesquisa binária é comumente conhecida como pesquisa de meio intervalo ou pesquisa logarítmica .
Neste tutorial de algoritmo, você aprenderá:
- O que é pesquisa?
- O que é pesquisa binária?
- Como funciona a pesquisa binária?
- Exemplo de pesquisa binária
- Por que precisamos da pesquisa binária?
Como funciona a pesquisa binária?
A pesquisa binária funciona da seguinte maneira:
- O processo de pesquisa é iniciado localizando o elemento do meio da matriz classificada de dados
- Depois disso, o valor-chave é comparado com o elemento
- Se o valor-chave for menor do que o elemento do meio, as pesquisas analisam os valores superiores para o elemento do meio para comparação e correspondência
- No caso do valor-chave ser maior do que o elemento do meio, as pesquisas analisam os valores mais baixos para o elemento do meio para comparação e correspondência
Exemplo de pesquisa binária
Vejamos o exemplo de um dicionário. Se você precisa 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:
- Você tem uma matriz de 10 dígitos e o elemento 59 precisa ser encontrado.
- Todos os elementos são marcados com o índice de 0 a 9. Agora, o meio da matriz é calculado. Para fazer isso, você pega os valores mais à esquerda e mais à direita do índice e os divide por 2. O resultado é 4,5, mas pegamos o valor mínimo. Portanto, o meio é 4.
- O algoritmo descarta todos os elementos do meio (4) para o limite inferior porque 59 é maior que 24 e agora a matriz fica com apenas 5 elementos.
- Agora, 59 é maior que 45 e menor que 63. O meio é 7. Portanto, o valor do índice direito torna-se médio - 1, que é igual a 6, e o valor do índice esquerdo permanece o mesmo de antes, que é 5.
- Nesse ponto, você sabe que 59 vem depois de 45. Portanto, o índice esquerdo, que é 5, também se torna o meio.
- 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
- Você tem uma matriz de valores classificados variando de 2 a 20 e precisa localizar 18.
- A média dos limites inferior e superior é (l + r) / 2 = 4. O valor pesquisado é maior do que o meio, que é 4.
- Os valores da matriz menores que o meio são retirados da pesquisa e os valores maiores que o valor médio 4 são pesquisados.
- 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 motivos a seguir tornam a pesquisa binária a melhor escolha para ser usada como um algoritmo de pesquisa:
- A pesquisa binária funciona de forma eficiente em dados classificados, não importa o tamanho dos dados
- Em vez de realizar a pesquisa percorrendo os dados em uma 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 usar comparações de igualdade, que são mais lentas e quase sempre imprecisas.
- Após cada ciclo de pesquisa, o algoritmo divide o tamanho do array pela metade, portanto, na próxima iteração ele funcionará apenas na metade restante do array
Resumo
- A 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 ao meio em cada iteração sob o elemento necessário encontrado.
- O algoritmo binário pega o meio da matriz dividindo a soma dos valores de índice mais à esquerda e à direita por 2. Agora, o algoritmo descarta 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.