DEV Community

Lucas Aranha
Lucas Aranha

Posted on • Edited on

2

Busca binária em Vetor

Olá pessoas!

Tentarei publicar algumas anotações e aprendizados à respeito de Estruturas de Dados para, além de fixar melhor o conteúdo, poder contribuir com uma visão mais abstrata da lógica, facilitando a implementação do código.

A primeira postagem é sobre a Busca Binária:

Vamos supor que, dado um vetor ordenado de tamanho qualquer, você queira encontrar um determinado número que possa estar dentro dessa estrutura.

No exemplo a seguir iremos utilizar um vetor com 10 posições, ou seja, seu índice vai de 0 à 9.
Alt Text

A busca binária consiste na ideia de "quebrar o código ao meio" e checar se o elemento está a esquerda ou a direita, quebrando o vetor em metades, se assim podemos dizer.

Como sabemos que esse vetor é ordenado, podemos pensar da seguinte forma: se o valor encontrado no vetor for maior que o elemento que estamos procurando, o "indicador" deve andar para a direita, caso contrário, ele irá para a esquerda.

Você pode definir duas variáveis: "início" e "final", onde a primeira começa em 0 e a segunda, em n-1, sendo n o tamanho do vetor. Outra variável deve ser criada, ela será responsável por "direcionar" a procura do elemento no vetor. Chamaremos-a de "meio".

O índice receberá o resultado da aritmética: (0 + 9)/2, seguindo nosso exemplo. Portanto, como é inteiro, a variável "meio" terá valor 4.

Partiremos de Vet[meio] para checar seu conteúdo e definir pra onde iremos.
Alt Text

O elemento que queremos encontrar é maior ou menor que Vet[meio]?
Se for maior, todos os números menores que Vet[meio] e até o próprio, serão descartados da busca. Portanto, precisamos somente atualizar a variável início para seu novo valor.

O algoritmo consiste em trabalhar dessa forma até encontrar o valor
desejado.
A próxima iteração trará o início com seu novo valor e o meio ancorado na metade do que sobrou do vetor. Veja:
Alt Text

Novamente, perceba que desta vez o elemento é maior que o conteúdo do índice do vetor, manipularemos a variável início para que descarte o valor inferior:
Alt Text

E por fim, o algoritmo retorna a posição onde está alocado o elemento procurado:
Alt Text

A vantagem é simples: pense em um vetor de 1000 posições. Uma busca linear, em seu pior caso, teria 1000 iterações; Já a busca binária, somente 10. (considerando que o valor estará no vetor).

Referências bibliográficas:

BACKES, André. Estruturas de Dados Descomplicada - Em Linguagem C. Rio de Janeiro: Elsevier, 2016.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up