Algoritmo para encontrar o elemento de pico de um array

As operações de busca em arrays não ordenados ou ordenados são extremamente diversificadas. Dependendo do cenário, talvez seja necessário procurar pelo maior elemento da estrutura. Em outras ocasiões, o menor elemento pode ser o alvo. Os itens repetidos, ou até mesmo os únicos, também são pesquisados com frequência.

Além dos exemplos supracitados, o algoritmo que localiza o índice ou posição do elemento de pico figura entre as rotinas de pesquisa mais populares no meio da programação. Assim como os seus pares, o procedimento em questão possui implementações distintas, cada uma com a sua respectiva complexidade de tempo.

Entendendo o problema

Antes do desenvolvimento e análise técnica das variações do algoritmo, a compreensão dos conceitos que estão por trás do elemento de pico é imprescindível. De modo a tornar isso possível, as cinco afirmações abaixo devem ser lidas com atenção.

1. Todo array com pelo menos dois itens tem um elemento de pico.
2. Todo elemento de pico supera ou iguala numericamente os seus vizinhos.
3. Se um array estiver ordenado de maneira ascendente, o último número sempre será o elemento de pico.
4. Se um array estiver ordenado de maneira descendente, o primeiro número sempre será o elemento de pico.
5. Se um array possuir apenas itens duplicados, o número exclusivo presente na estrutura será o elemento de pico.

A segunda frase da lista representa a principal característica de um elemento de pico. Obrigatoriamente, pensando nos limites de um vetor, esse tipo de número deve ser maior do que o seu último antecessor e do que seu primeiro sucessor, se ambos existirem. 

Traduzindo a teoria descrita até então em prática, considere o array hipotético composto por [1, 4, 5, 7, 3, 2]. O elemento de pico dessa estrutura de dados está nitidamente na posição três, representado portanto pelo número sete. Esse é o único item do vetor que excede os valores de seus vizinhos, neste caso os números cinco e três.

Usando complexidade linear de tempo para resolver o problema

A partir dos fundamentos da busca linear, o elemento de pico de qualquer array pode ser facilmente determinado. Para isso, basta percorrer o vetor de input em sua totalidade, verificando a cada iteração se o elemento atual supera ou iguala os seus vizinhos.

Complementando a busca linear, o algoritmo trata de dois corner cases no início da sua implementação, que otimizam o processo de pesquisa de acordo com o array analisado. Dessa forma, o passo a passo completo do método pode ser detalhado sem grandes dificuldades.

1. A função checa se o primeiro elemento do vetor arr é maior do que o elemento seguinte. Nessa situação, o elemento de pico está no começo da estrutura. Logo, a rotina retorna o índice zero.
2. A função checa se o último elemento do vetor arr é maior do que o elemento anterior. Nessa circunstância, o elemento de pico está no fim da estrutura. Por isso, o método retorna o índice n - 1.
3. Supondo que o elemento de pico não esteja nos limites do array arr, a função aplica uma busca linear. Iteração após iteração, o algoritmo procura pelo elemento que ultrapasse ou iguale os seus pares. À vista disso, o valor do índice i é retornado somente quando tal condição for satisfeita.

Usando complexidade logarítmica de tempo para resolver o problema

A performance do algoritmo que acabou de ser apresentado sofre uma degradação conforme o vetor de input cresce em quantidade de elementos. Levando em conta os sistemas que processam volumes notáveis de dados, esse fator passa a ser um impeditivo incômodo.

Com o intuito de melhorar o desempenho da função de pesquisa, ou seja, migrar de uma complexidade linear para uma complexidade logarítmica de tempo, os princípios da busca binária devem ser prontamente aderidos e adaptados.

Em linhas gerais, o algoritmo de fato se beneficia da solução padrão da busca binária. Contudo, ele acrescenta algumas verificações próprias que garantem a conclusão da pesquisa dentro da mesma complexidade logarítmica de tempo.

1. A variável esquerda é declarada com o objetivo de definir o limite de busca inferior no vetor arr. O seu valor inicial aponta para o primeiro índice da estrutura.
2. A variável direita é declarada com o propósito de estabelecer o limite de busca superior no vetor arr. O seu valor inicial aponta para o último índice da estrutura.
3. A variável metade é declarada para armazenar o índice do elemento intermediário do vetor arr.
4. Enquanto o limite superior for maior ou igual em relação ao limite inferior, o algoritmo executa os passos elencados a seguir. Porém, quando essa condição não for mais verdadeira, o método retorna o valor fixo de menos um. Isso indica que o elemento de pico não foi encontrado.
5. A variável metade recebe o índice do elemento intermediário atual, a partir de uma divisão por dois da soma dos limites esquerda e direita.
6. Se o valor da variável metade for igual a zero, isto é, referenciar o primeiro item do vetor arr, e o número armazenado nesta posição superar ou igualar o número no índice seguinte (metade + 1), a função terá encontrado o elemento de pico no início da estrutura.
7. Se o valor da variável metade for igual a n - 1, isto é, referenciar o último item do vetor arr, e o número armazenado nesta posição superar ou igualar o número no índice antecessor (metade - 1), a função terá encontrado o elemento de pico no término da estrutura.
8. Se o número armazenado na posição metade superar ou igual o número no índice antecessor (metade - 1), bem como no índice sucessor (metade + 1), a função terá encontrado o elemento de pico no meio da estrutura.
9. Se o elemento intermediário for menor do que o seu predecessor (metade - 1), o método encurta o intervalo de pesquisa para a metade inferior do vetor arr (direita = metade - 1).
10. Se o elemento intermediário for maior do que o seu predecessor (metade - 1), o método encurta o intervalo de pesquisa para a metade superior do vetor arr (esquerda = metade + 1).

Analisando a complexidade das soluções

Examinando os algoritmos sob a óptica do consumo do espaço auxiliar de memória, ambos localizam o elemento de pico sem a necessidade de usar estruturas auxiliares dependentes do input e de fazer chamadas recursivas. Sendo assim, as duas funções possuem uma complexidade constante de memória.

Entretanto, as semelhanças terminam no comparativo envolvendo a complexidade de tempo dos métodos. Dado que o primeiro algoritmo segue a base da busca linear, percorrendo todos os elementos do vetor de input, e o segundo algoritmo se mantém fiel às premissas da busca binária, reduzindo drasticamente o intervalo de pesquisa, a diferença de performance é muito relevante.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[10]	Média de tempo13.04 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[10]	Média de tempo15.44 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[100]	Média de tempo153.94 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[100]	Média de tempo24.59 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[1000]	Média de tempo1,971.10 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[1000]	Média de tempo40.12 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[10000]	Média de tempo20,210.25 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[10000]	Média de tempo66.64 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[100000]	Média de tempo223,740.73	Espaço alocado-
MétodoComplexidadeLogaritmica	InputInt32[100000]	Média de tempo82.73 ns	Espaço alocado-

Partindo de um processamento simples, no qual o array de input tem apenas dez elementos, a função de complexidade linear bate a logarítmica por pouquíssimos nano segundos. Todavia, há uma virada de mesa logo no segundo cenário de cem elementos. O método de complexidade logarítmica ultrapassa o linear em quase sete vezes, demonstrando um desempenho soberano.

Essa conjuntura se confirma nos testes com mil, dez mil e cem mil elementos, nos quais o algoritmo de complexidade logarítmica ostenta um ganho de setenta e oito, trezentos e seis e dois mil e setecentos e trinta vezes, 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.