Algoritmo de pesquisa binária: função, benefícios, complexidade de tempo e espaço

Introdução

Em qualquer sistema computacional, a busca é uma das funcionalidades mais críticas a serem desenvolvidas. As técnicas de pesquisa são usadas em recuperações de arquivos, indexação e muitas outras aplicações. Existem muitas técnicas de pesquisa disponíveis. Uma delas é a técnica de busca binária.

Um algoritmo de busca binária funciona com a ideia de negligenciar metade da lista em cada iteração. Ele continua dividindo a lista até encontrar o valor que está procurando em uma determinada lista. Um algoritmo de pesquisa binária é uma atualização rápida para um algoritmo de pesquisa linear simples.

Nenhuma experiência de codificação necessária. Suporte de carreira 360°. Diploma PG em Machine Learning & AI do IIIT-B e upGrad.

Funcionamento de um algoritmo de busca binária

A primeira coisa a notar é que um algoritmo de busca binária sempre funciona em uma lista ordenada. Portanto, o primeiro passo lógico é classificar a lista fornecida. Após a ordenação, a mediana da lista é verificada com o valor desejado.

• Se o valor desejado for igual ao valor do índice central, o índice será retornado como resposta.

• Se o valor de destino for menor que o índice central da lista, o lado direito da lista será ignorado.

• Se o valor desejado for maior que o valor do índice central, a metade esquerda é descartada.

• O processo é então repetido em listas reduzidas até que o valor alvo seja encontrado.

Exemplo 1

Vejamos o algoritmo com um exemplo. Suponha que haja uma lista com os seguintes números:

1, 15, 23, 7, 6, 14, 8, 3, 27

Vamos tomar o valor desejado como 27. O número total de elementos na lista é 9.

O primeiro passo é ordenar a lista. Após a classificação, a lista ficaria mais ou menos assim:

1, 3, 6, 7, 8, 14, 15, 23, 27

Como o número de elementos da lista é nove, o índice central seria cinco. O valor no índice cinco é 8. O valor desejado, 27, é comparado com o valor 8. Primeiro, verifique se o valor é igual a 8 ou não. Se sim, retorne o índice e saia.

Como 27 é maior que 8, ignoramos a parte esquerda e percorremos apenas o lado direito da lista. A nova lista a percorrer é:

14, 15, 23, 27

Nota: Na prática, a lista não é truncada. Apenas a observação é estreitada. Portanto, a “nova lista” não deve ser confundida com fazer uma nova lista ou encurtar a original. Embora possa ser implementado com uma nova lista, existem dois problemas. Primeiro, haverá uma sobrecarga de memória. Cada nova lista aumentará a complexidade do espaço. E segundo, os índices originais precisam ser rastreados em cada iteração.

O novo índice central pode ser considerado como o segundo ou terceiro elemento, dependendo da implementação. Aqui, vamos considerar o terceiro elemento como central. O valor 23 é comparado com o valor 27. Como o valor é maior que o valor central, descartaremos a metade esquerda.

A lista a percorrer é:

27

Como a lista contém apenas um único elemento, ele é considerado o elemento central. Assim, comparamos o valor desejado com 27. Conforme eles correspondem, retornamos o valor de índice de 27 na lista original.

Exemplo #2

Na mesma lista, vamos supor que o valor desejado seja 2.

Primeiro, o valor central oito é comparado com 2. Como o valor desejado é menor que o valor central, reduzimos nosso foco para o lado esquerdo da lista.

A nova travessia consistirá em:

1, 3, 6, 7

Tomemos o elemento central como o segundo elemento. O valor desejado dois é comparado com 3. Como o valor ainda é menor, novamente reduzimos o foco para o lado esquerdo da lista.

A nova travessia consistirá em:

1

Como a lista de deslocamento possui apenas um elemento, o valor é comparado diretamente com o elemento restante. Vemos que os valores não coincidem. Portanto, saímos do loop com uma mensagem de erro: v alor não encontrado .

Certificação avançada em ciência de dados, mais de 250 parceiros de contratação, mais de 300 horas de aprendizado, 0% EMI

Complexidade de tempo e espaço

A complexidade de tempo do algoritmo de busca binária é O(log n). A complexidade de tempo do melhor caso seria O(1) quando o índice central correspondesse diretamente ao valor desejado. O pior cenário pode ser os valores em qualquer extremidade da lista ou valores que não estão na lista.

A complexidade do espaço do algoritmo de busca binária depende da implementação do algoritmo. Existem duas formas de implementá-lo:

1. Método iterativo
2. Método recursivo

Ambos os métodos são praticamente os mesmos, com duas diferenças na implementação. Primeiro, não há loop no método recursivo. Segundo, em vez de passar os novos valores para a próxima iteração do loop, ele os passa para a próxima recursão. No método iterativo, as iterações podem ser controladas através das condições de loop, enquanto no método recursivo, o máximo e o mínimo são usados ​​como condição de contorno.

No método iterativo, a complexidade do espaço seria O(1). Já no método recursivo, a complexidade do espaço seria O(log n).

Benefícios

• Um algoritmo de busca binária é um algoritmo de busca bastante simples de implementar.

• É uma melhoria significativa em relação à pesquisa linear e executa quase o mesmo em comparação com alguns dos algoritmos de pesquisa mais difíceis de implementar.

• O algoritmo de busca binária divide a lista pela metade em cada iteração, em vez de vasculhar sequencialmente a lista. Em listas grandes, esse método pode ser muito útil.

Checkout: Classificação da árvore de decisão: tudo o que você precisa saber

Conclusão

Um algoritmo de busca binária é um algoritmo amplamente utilizado no domínio computacional. É um algoritmo de pesquisa gordo e preciso que pode funcionar bem em conjuntos de dados grandes e pequenos. Um algoritmo de busca binária é um algoritmo simples e confiável de implementar. Com a análise de tempo e espaço, os benefícios do uso dessa técnica específica são evidentes.

Se você está curioso para aprender sobre ciência de dados, confira o PG Diploma in Data Science do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1- on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.