Busca binária

Definição - o que significa pesquisa binária?

Um algoritmo de pesquisa binária é usado para encontrar a posição de um valor específico contido em uma matriz classificada. Trabalhando com o princípio de dividir e conquistar, esse algoritmo de pesquisa pode ser bastante rápido, mas a ressalva é que os dados precisam estar em uma forma classificada. Ele funciona iniciando a pesquisa no meio da matriz e descendo a primeira metade inferior ou superior da sequência. Se o valor da mediana for inferior ao valor de destino, isso significa que a pesquisa precisa ser mais alta; caso contrário, ela precisa olhar para a parte descendente da matriz.

Uma pesquisa binária também é conhecida como pesquisa de meio intervalo ou pesquisa logarítmica.

Definirtec explica a pesquisa binária

Uma pesquisa binária é um método rápido e eficiente de encontrar um valor-alvo específico em um conjunto de itens ordenados. Começando no meio da lista classificada, ele pode efetivamente cortar o espaço de pesquisa pela metade, determinando se deve subir ou descer a lista com base no valor médio em comparação com o valor de destino.

Por exemplo, com um valor alvo de 8 e um espaço de pesquisa de 1 a 11:

  1. O valor médio / médio é encontrado e o ponteiro é colocado lá, que neste caso é 6.
  2. A meta de 8 é comparada a 6. Como 6 é menor que 8, a meta deve estar na metade superior.
  3. O ponteiro é movido para o próximo valor (7) e comparado ao destino. É menor, portanto, o ponteiro se move para o próximo valor mais alto.
  4. O ponteiro está agora em 8. Comparando-o com o alvo, é uma correspondência exata, portanto, o alvo foi encontrado.

Usando a pesquisa binária, o alvo só teve que ser comparado a três valores. Em comparação com uma pesquisa linear, ela teria começado do primeiro valor e subido, precisando comparar o alvo com oito valores. Uma pesquisa binária só é possível com um conjunto ordenado de dados; se os dados forem organizados aleatoriamente, uma pesquisa linear produzirá resultados o tempo todo, enquanto uma pesquisa binária provavelmente ficará presa em um loop infinito.