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.

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.

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:

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:

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

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.