image

Access unlimited bootcamps and 650+ courses forever

60
%OFF
Article image
Isadora Ariane
Isadora Ariane12/11/2024 14:56
Share

TOP 25 ALGORITMOS | Binary Search

  • #Estrutura de dados

É um algoritmo de busca usado em arrays organizados de forma crescente. Ele funciona dividindo repetidamente o intervalo de busca pela metade comparando o elemento alvo com o valor mediano do espaço de busca até que o elemento alvo seja encontrado, ou este intervalo esteja vazio.

// javascript //

function binarySearch(array, x){

  let extremidade_menor = 0;
  let extremidade_maior = array.length - 1;
  let meio;

  while (extremidade_maior >= extremidade_menor) {
      meio = extremidade_menor + Math.floor((extremidade_maior - extremidade_menor) / 2);

      // Se o elemento estiver presente no próprio meio
      if (array[meio] == x)
          return meio;

      // Se o elemento for menor que o meio, ele só poderá estar presente no subarray esquerdo
      if (array[meio] > x)
          extremidade_maior = meio - 1;

      // Caso contrário, o elemento só pode estar presente no subarray direito
      else
          extremidade_menor = meio + 1;
  }

  //Chegamos aqui quando o elemento não está presente no array
  return -1;
}

🕰️ | Complexidade do Tempo

Como o tempo de processamento cresce na mesma proporção que o tamanho do input, portanto, a complexidade do tempo será O(log N).

📦 | Complexidade do Espaço

Como não há necessidade de utilização de outra variável a complexidade será de O(1).

✔️ | Vantagens

✦ Não requer memória adicional;

✦ Adequado para grandes conjuntos de dados;

❌ | Desvantagens

✦ Depende da organização do array;

✦ Depende do tipo de dados do array (devem ser iguais);

📁 | Resumo

image

Share
Comments (0)