close

Algoritmo de Busca Binária (Binary Search) em PHP: Explicação, Passos e Exemplo

O algoritmo Binary Search é um método eficiente para encontrar um valor específico em uma matriz classificada. Essa abordagem divide a matriz em partes menores e compara continuamente o valor na posição intermediária do intervalo de pesquisa com o valor de destino. Se os valores corresponderem, o valor desejado será encontrado; caso contrário, o algoritmo continua a restringir o intervalo de pesquisa e repete o processo até que o valor seja encontrado ou não haja mais elementos para examinar.

Passos:

  1. Inicializar o intervalo de pesquisa: Comece selecionando o intervalo de pesquisa da primeira left  à última posição right  da matriz.
  2. Encontre o ponto médio: Calcule o ponto médio calculando a média das left posições e direita; este é o ponto médio do intervalo de pesquisa.
  3. Comparar valores: compare o valor no ponto médio com o valor alvo.
  4. Lidar com o resultado da comparação: se o valor no ponto médio corresponder ao valor de destino, retorne esta posição. Se o valor no ponto médio for menor que o valor alvo, atualize a posição esquerda para meio + 1 para pesquisar a metade direita. Se o valor no ponto médio for maior que o valor alvo, atualize a posição direita para o meio- 1 para pesquisar a metade esquerda.
  5. Repita: Repita as etapas 2 a 4 até que o valor seja encontrado ou não haja mais elementos para verificar left > right.

Vantagens e desvantagens

Vantagens:

  • Desempenho eficiente: a complexidade de tempo do algoritmo é O(log n), tornando-o altamente eficiente para lidar com grandes conjuntos de dados.
  • Eficaz para grandes conjuntos de dados: a pesquisa binária é eficaz na redução do número de elementos para examinar rapidamente grandes conjuntos de dados.

Desvantagens:

  • Aplicável apenas a arrays ordenados: O algoritmo só funciona em arrays ordenados.
  • Número variável de etapas: O número de etapas necessárias para encontrar o valor depende de sua posição na matriz e pode levar muitas etapas para valores próximos às extremidades.

Exemplo: Busca Binária para encontrar o valor 12 em um array ordenado em PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Explicação do Exemplo

  1. Começamos com o intervalo de pesquisa inicial da primeira posição left = 0 até a última posição right = 6  da matriz.
  2. Calculamos o ponto médio(meio) calculando a média das posições esquerda e direita; mid = 3. O valor no meio é 12.
  3. Comparamos o valor em mid(12) com o valor alvo(12) e encontramos uma correspondência, então retornamos a posição 3.
  4. O algoritmo termina e exibimos o resultado "Valor 12 encontrado na posição 3".