Um dos conceitos mais importantes dentro da ciência da computação atualmente se refere à busca de dados dentro de uma estrutura. Com o número de informações disponíveis na rede, a busca eficiente por um elemento se tornou parte importante do trabalho de um desenvolvedor de software. Diante disso, surgem dois principais métodos de busca: o algorítimo de busca sequencial e o algoritmo de busca binária.
Busca Sequencial
Como o próprio nome já sugere, o algorítimo de busca sequencial — podendo ser chamado também de busca linear — é uma estrutura de dados que percorre cada elemento de um vetor até encontrar o valor desejado. O algorítimo sequencial possui complexidade O(n), ou seja: apesar de funcionar para vetores com poucos elementos, o mesmo pode se tornar custoso na medida em que o número de elementos dentro do vetor cresce, tendo seu pior caso o enésimo elemento de um determinado array: A = {0... N-1}.
Veja o exemplo de um algoritmo de busca linear abaixo:
É importante notar no código acima que, apesar do vetor estar desorganizado, isso não altera o retorno da função. Isso ocorre porque o algoritmo de busca sequencial independe do vetor estar ordenado para funcionar!
Busca Binária
Se a busca sequencial pode se tornar custosa a medida em que o número de elementos dentro de um vetor cresce, o algoritmo de busca binária surge como uma maneira mais eficiente de encontrar um elemento dentro de um array.
Tendo seu tempo de execução O(log n), o algoritmo funciona verificando o item que está no meio do vetor, e caso não seja o valor correto, podemos eliminar uma das metades do array. A partir disso, ele divide repetidamente a metade que possivelmente contem o item, até que a lista seja reduzida somente em um elemento.
Dividindo o número de elementos presentes no vetor a cada execução, o algoritmo binário diminui o número de interações necessárias para encontrar o elemento desejado, tornando-o assim mais eficiente que o algoritmo linear.
Abaixo uma comparação gráfica entre os dois:
Por levar em consideração os maiores e menores números de um vetor para fazer a divisão, o algorítimo de busca binária obrigatoriamente precisa de um array ordenado para funcionar. Por conta disso, pode ser necessária a utilização de um algoritmo de ordenação antes de utilizá-lo.
Top comments (0)