Algoritmo para encontrar a primeira ocorrência de um número em um array ordenado

No dia a dia dos projetos de software, a necessidade de realizar operações de busca em estruturas de dados costuma ser recorrente. Seja para obter o índice, ou até mesmo o próprio valor do elemento, o desenvolvedor encarregado por este tipo de funcionalidade tem o desafio de implementá-la com o melhor desempenho.

Entretanto, na maioria das vezes, devido ao desconhecimento de soluções mais eficientes ou à urgência de entregar a sua atividade, o programador constrói uma função mal otimizada. Isso quer dizer que, sobretudo em cenários nos quais o input processado possui um tamanho considerável, o código-fonte não reage bem, consumindo muito tempo de execução.

Pensando justamente em situações semelhantes à supracitada, que esta publicação analisará duas versões com complexidades distintas de um algoritmo de pesquisa, o qual se propõe a encontrar a primeira ocorrência de um número em qualquer array ordenado.

Entendendo o problema

A compreensão deste problema é uma tarefa simples e intuitiva. Imagine que seja preciso determinar a ocorrência inicial do número cinco em um vetor ordenado formado pelos números [1, 2, 3, 4, 5, 5, 7, 9].

Com base em uma breve observação feita na estrutura hipotética, é possível concluir que o quarto índice do array demarca a primeira aparição do elemento alvo. Por exemplo, se o número nove estivesse sendo procurado, o resultado seria o sétimo e último índice do vetor, e assim sucessivamente.

Usando complexidade linear de tempo para resolver o problema

O algoritmo com menor desempenho localiza o índice da ocorrência original do número em complexidade linear de tempo. Ou seja, na pior conjuntura concebível, a função verifica todos os itens do array passado como input.

A partir da implementação compartilhada no bloco de código acima, os desenvolvedores mais familiarizados com a análise de algoritmos devem constatar que o método utiliza os fundamentos da busca linear para retornar o resultado do problema.

1. Um loop for percorre o vetor arr do início até o seu fim para procurar o elemento pesquisado.
2. A cada iteração, o método checa se o item atual de arr possui o mesmo valor do número x que está sendo buscado. Se essa condição em algum momento for verdadeira, o índice i é retornado.
3. Se a varredura no array arr for finalizada, isto significa que x não está presente na estrutura. Quando isso ocorrer, a função retorna o valor fixo do número um na sua versão negativa.

Usando complexidade logarítmica de tempo para resolver o problema

Frequentemente, a aplicação dos princípios da busca binária melhora a eficácia das soluções para desafios que envolvem a consulta de um elemento específico. Essa mesma premissa se mostra válida no contexto da procura pela primeira ocorrência de um número em vetores ordenados.

Dado que a nova função apresentada usufrui de boa parte da lógica original da busca binária, a sua complexidade de tempo atinge o patamar logarítmico. Portanto, conforme evidenciado mais adiante neste artigo, os ganhos em relação à abordagem linear são notavelmente expressivos.

1. A função verifica se o limite de busca superior é maior ou igual ao limite de busca inferior. Supondo que a condição seja falsa, isto representa que a busca binária não pode ser realizada no array arr. Logo, o procedimento retorna o número um negativo, indicando que o valor de x não foi encontrado na estrutura.
2. Por outro lado, se o intervalo de pesquisa estiver adequado, o método divide o vetor arr na metade.
3. Na hipótese do índice metade apontar para o índice inicial do array arr, ou se o elemento buscado x for maior que o número presente no índice antecessor de metade, e além disto o item na posição simbolizada por metade possuir o mesmo valor do que x, isto indica que a resposta do problema foi descoberta e a função retorna o índice metade.
4. Se o valor de x for maior do que o elemento que está no índice metade, o limite inferior do intervalo de pesquisa no vetor arr é modificado (aumentado) pelo algoritmo.
5. Se o valor de x for menor do que o elemento que está no índice metade, o limite superior do intervalo de pesquisa no vetor arr é modificado (diminuído) pelo algoritmo.

Analisando a complexidade das soluções

De acordo com o que foi analisado até então, as duas funções diferem no que tange a complexidade de tempo. Enquanto a primeira delas itera por todos os elementos do array passado como input, ostentando assim uma complexidade linear, em contrapartida a segunda rotina utiliza uma estratégia mais inteligente baseada na busca binária, possuindo por consequência uma complexidade logarítmica.

A discrepância entre os algoritmos fica mais evidente em termos numéricos. Com a assistência da biblioteca BenchmarkDotNet, calculou-se a média de tempo para diversos cenários de execução de ambos os métodos.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[10]	Média de tempo4.483 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[10]	Média de tempo6.809 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[100]	Média de tempo40.429 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[100]	Média de tempo11.922 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[200]	Média de tempo72.923 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[200]	Média de tempo13.869 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[300]	Média de tempo104.038 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[300]	Média de tempo16.103 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[1000]	Média de tempo335.095 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[1000]	Média de tempo18.086 ns	Espaço alocado-

Partindo do menor input testado, um vetor composto por dez números ordenados quaisquer, o MétodoComplexidadeLinear obteve um desempenho ligeiramente acima do MétodoComplexidadeLogaritmica. Contudo, a partir do input de cem elementos, há uma virada de mesa surpreendente, na qual o MétodoComplexidadeLogaritmica apresenta uma performance quase quatro vezes superior.

Depois disso, a distância cresce ainda mais, tendo em vista que para duzentos, trezentos e mil itens, o MétodoComplexidadeLogaritmica adquire uma vantagem de cinco, seis e dezoito vezes em relação ao MétodoComplexidadeLinear, respectivamente.

O código-fonte completo dos algoritmos e os detalhes extras acerca do desempenho de cada um deles estão disponíveis no meu repositório do Github.