Estrutura de dados e algoritmos de pesquisa binária

A pesquisa binária é um algoritmo de pesquisa rápida com complexidade de tempo de execução de Ο (log n). Este algoritmo de busca funciona com o princípio de dividir para conquistar. Para que esse algoritmo funcione corretamente, a coleta de dados deve estar na forma classificada.

A pesquisa binária procura um item específico, comparando o item mais central da coleção. Se ocorrer uma correspondência, o índice do item será retornado. Se o item do meio for maior do que o item, então o item é pesquisado na submatriz à esquerda do item do meio. Caso contrário, o item é pesquisado na submatriz à direita do item do meio. Este processo continua na submatriz também até que o tamanho da submatriz seja reduzido a zero.

Como funciona a pesquisa binária?

Para que uma pesquisa binária funcione, é obrigatório que a matriz de destino seja classificada. Aprenderemos o processo de busca binária com um exemplo pictórico. A seguir está nossa matriz classificada e vamos supor que precisamos pesquisar a localização do valor 31 usando a pesquisa binária.

Primeiro, devemos determinar metade da matriz usando esta fórmula -

mid = low + (high - low) / 2

Aqui está, 0 + (9 - 0) / 2 = 4 (valor inteiro de 4,5). Portanto, 4 é o meio da matriz.

Agora comparamos o valor armazenado no local 4 com o valor que está sendo pesquisado, ou seja, 31. Descobrimos que o valor no local 4 é 27, o que não é uma correspondência. Como o valor é maior que 27 e temos uma matriz classificada, também sabemos que o valor de destino deve estar na parte superior da matriz.

Mudamos nosso mínimo para médio + 1 e encontramos o novo valor médio novamente.

low = mid + 1
mid = low + (high - low) / 2

Nosso novo mid é 7 agora. Comparamos o valor armazenado no local 7 com nosso valor alvo 31.

O valor armazenado na localização 7 não corresponde, mas é mais do que procuramos. Portanto, o valor deve estar na parte inferior deste local.

Portanto, calculamos o meio novamente. Desta vez, são 5.

Comparamos o valor armazenado no local 5 com nosso valor alvo. Descobrimos que é uma combinação.

Concluímos que o valor alvo 31 é armazenado na localização 5.

A pesquisa binária divide pela metade os itens pesquisáveis ​​e, portanto, reduz a contagem de comparações a serem feitas a muito menos números.

Pseudo-código

O pseudocódigo dos algoritmos de pesquisa binária deve ser semelhante a este -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Para saber sobre a implementação de pesquisa binária usando array na linguagem de programação C, clique aqui .