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
