DEV Community

Cover image for TOP 25 ALGORITMOS | Binary Search
Isadora Ariane
Isadora Ariane

Posted on

TOP 25 ALGORITMOS | Binary Search

É 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;
}
Enter fullscreen mode Exit fullscreen mode

🕰️ | 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 description

Imagine monitoring actually built for developers

Billboard image

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay