Algoritmos são sequências de instruções para se resolver um determinado problema, contudo eles podem variar em efiência e perfomance para resolução do mesmo. Dito isto, seu estudo é importante para qualquer programador, pois muitas vezes ja pegamos "coisas prontas" e usamos indiscriminadamente sem entender os trade-offs das mesmas. Isso limita o programador e sua visão criativa/resolutiva, ou seja, ele é dominado pelas ferramentas que usa.
Conceitos Básicos
O algoritmo que iremos ver é o de busca binária (binary search), sendo o nome bem sugestivo podemos ter uma ideia do problema que ele resolve.
Imaginemos que você tenha que achar a pagina 567, porque por algum motivo você perdeu o marcador de novo, em um livro de 1000 paginas. Como você faria essa busca ? O mais comum a se fazer seria começar a busca pelo meio, certo ? Pois, a pagina 567 fica mais próxima do meio do livro. Com certeza, essa uma maneira bem mais rápida de buscar, do que olhar pagina por pagina.
O conceito de busca binária não é muito diferente do exemplo do livro, mas irei ilustrar com um exemplo um pouco melhor, menos livroso. Você está tentando adivinhar número de meias listradas (que é 57) que uma pessoa tem, ela irá te dizer se você disse um número muito acima ou baixo da atual quantidade, entre 1 a 100.
Há duas maneiras de resolver este problema:
Busca simples
Podemos começar pelo número 1, 2, 3, 4, 5... e assim por diante, estando essas tentativas muito abaixo do número atual de meias listradas e continuaremos a verificar item por item até o número desejado.
Busca binária
Outra opção seria começar pelo meio, no caso, o número 50 que ainda está abaixo da quantidade atual. Sabendo disso podemos eliminar a metade (1 a 50, nos restando de 51 a 100) e tentar novamente, por exemplo 58, mas ainda é um valor acima do número que procuramos, mais uma vez eliminamos a metade (de 58 a 100, nos restando de 52 a 57) e tentamos novamente. Podemos tentar agora 57 e acertamos a quantidade das benditas meias listradas. Veja o exemplo escrito em C logo abaixo:
// Bem, aqui estamos passando uma lista de inteiros e o seu tamanho (uma cortesia do C)
int binary_search(int itens[], int length)
{
int abaixo = 0;
int acima = length - 1;
// O nosso intuito é iniciar nossa busca pelo meio da lista
int meio = length - 1 / 2;
// Item que desejamos achar
int item_desejado = 5;
while (abaixo <= acima)
{
// Atualizando o nosso "novo meio"
meio = abaixo + acima;
// Nosso palpite sempre será o meio da nossa lista
int palpite = itens[meio];
// Se nosso palpite estiver certo, retornamos o lugar onde o item está
if (palpite == item_desejado)
return meio;
// Caso esteja errado, iremos verificar se o palpite está muito acima ou abaixo do esperado
if (palpite > item_desejado)
{
// Estando acima do esperado, cortamos metade das possibilidades acima
acima = meio - 1;
}
else
{
// Estando abaixo do esperado, cortamos metade das possibilidades abaixo
abaixo = meio + 1;
}
}
}
Contudo o algoritmo irá funcionar apenas com lista de dados ordenados, como [1,2,3] ou ["Ana", "Bob", "Carla"].
Mas você já deve estar conseguindo sentir o cheirinho das aplicações desse algoritmo no mundo real, como consultas em banco de dados ou pesquisa de uma música na sua playlist (se ordenada).
Top comments (0)