terça-feira, 20 de outubro de 2015

Maior elemento de um vetor unimodal

Olá pessoal, nesse post vamos construir um algoritmo de complexidade O(nlog(n)) para obter o maior elemento de um vetor unimodal.

Um vetor unimodal é um vetor que possui uma sequência crescente seguida de uma sequência decrescente.

Exemplo de vetor unimodal: 1, 9, 10, 6, 2.

Tem alguma ideia de como resolver isso com complexidade nlog(n)?

Nós iremos fazer uma busca binária, iremos comparar o elemento do meio com o seu antecessor e sucessor. Assim, podemos resolver facilmente utilizando recursividade. Veja o código:

Perceba que na linha 16 o elemento do meio foi comparado ao seu antecessor e sucessor, se o elemento do meio for maior que o seu antecessor e sucessor, então esse é o maior elemento do vetor unimodal.

Na linha 19 é verificado se o elemento do meio é menor do que o seu sucessor, se for, então continua a busca na parte mais à direita do vetor unimodal.

Na linha 22 é feita a busca na parte mais à esquerda do vetor unimodal.

Quaisquer dúvidas deixem nos comentários, até a próxima!


Nenhum comentário: