Anúncios

Busca binária

O objetivo deste post é apresentar um meio eficiente de busca de objetos em memória.

O surgimento da sintaxe LINQ, assim como a utilização de query methods, facilitou a busca em memória. Com estes recursos podemos facilmente executar queries em arrays, coleções e listas de tipos genéricos. O uso deste modelo de sintaxe agiliza o processo de desenvolvimento por tornar a busca em memória trivial e de simples codificação.

Mas, ao adotarmos esse modelo de sintaxe, estamos realmente escrevendo código performático? Será que essas consultas em memória são o modelo mais rápido de pesquisa? Não estaríamos perdemos poder computacional ou tempo de processamento ao adotar estes recursos em determinados cenários de pesquisa em memória?

Dada a necessidade de executar consultas eficientes e com baixo custo computacional, passamos a evitar consultas que consumam muitos recursos computacionais e que sejam lentas.

A busca binária é um algoritmo de busca que segue o paradigma da divisão e conquista. Partindo do pressuposto de que o conjunto de elementos está ordenado, são executadas diversas divisões do espaço de busca restringindo o possível local no qual o elemento buscado está posicionado. A imagem a seguir ilustra o processo de divisão do conjunto de elementos realizado pela busca de elementos.

clip_image002

Leia mais deste post

Anúncios