Pesquisa de bits

Vamos ver neste post duas formas de pesquisa que apresentam vantagens diferentes dependendo do tipo de dados que estamos utilizando. Consideraremos como exemplo a avaliação de uma sequencia de bits. Esta sequencia será passada para o programa como um vetor de inteiros, desta forma queremos achar o primeiro a[i] cujo valor é igual a 1, isto é, que divide o array em duas partes, a inferior contendo "0"s e a superior contendo "1"s.

O primeiro tipo de pesquisa que iremos utilizar é denominado busca linear ou busca sequencial. Este tipo de pesquisa é aplicado em vetores ou listas de modo sequencial, i. e., elemento por elemento, do menor para o maior (ou vice-versa). Deste modo o tempo de execução é função do do número de elementos. Num vetor ordenado, essa não é a pesquisa mais eficiente. No nosso caso veremos que se esperamos que existam poucos bits "0", esta será a melhor opção.

Uma outra pesquisa é a busca binária, onde o tempo de pesquisa é logaritmo em relação ao número de elementos. Este tipo de pesquisa segue o paradigma de dividir e conquistar um vetor ordenado. Funciona mediante sucessivas divisões do espaço de busca, comparando o elemento buscado (ou chave - no nosso caso o primeiro elemento com bit 1) com o elemento no meio do subvetor pesquisado. Este procedimento é facilmente implementado recursivamente.

Vamos ver nosso exemplo: