Ternary Search

Neste artigo exploramos uma variação do método de pesquisa binária que permite calcular máximos em funções bitónicas (ou unimodais). Veremos como este pequeno truque pode se útil em certos tipos de problemas.

Notem que este método não é apenas uma pesquisa binária com divisão em dois pontos em vez de um único.

Pesquisa Ternária

Vejamos um artigo sobre o assunto:

Adicionalmente podem verificar o artigo da Wikipedia:

Finalmente, vamos aplicar esta técnica num problema.

Não é óbvio como aplicar o método neste problema, por isso, se tiverem dúvidas consultem o editorial.

Intuição

Terminamos com algumas notas sobre casos comuns onde se pode aplicar pesquisa ternária.

Apesar de, no geral, perceber quando aplicar este método é uma arte, o mesmo se verifica para a pesquisa binária. A primeira coisa a fazer é procurar por funções ou propriedades do problema, que sejam bitónicas. Isto nem sempre é fácil e obriga a explorar várias alternativas, mas um caso simples de verificar que é bitónico é quando temos uma função que é uma soma de duas funções monotónicas (não é difícil provar isto, mas é fácil de perceber intuitivamente porquê). Um exemplo que segue este padrão é o problema 1, sugerido na secção anterior.