Neste artigo iremos generalizar os conceitos apresentados no artigo de pesquisa em listas. Iremos primeiro ver dois casos comuns e depois discutir a intuição do método.

Aplicações discretas

Se em vez de termos uma lista onde queremos procurar um determinado valor, podemos considerar que temos uma lista "implícita", por exemplo, se quisermos encontrar algo numa função monótona. Neste caso, se a função é monótona, então ou aumenta sempre ou diminui sempre, logo é possível aplicar o mesmo raciocínio do caso das listas. Vejamos isto com mais detalhe:

Artigo: Capítulo 3.2 do livro Competitive Programming 1

Ler o capítulo 3.2 do livro (a segunda parte já tem a ver com o método da secção seguinte). Quem tiver uma versão mais recente do livro, consulte a secção de título "Divide and Conquer".

Nota: Para quem não tem o livro

É normal que muitos não tenham uma cópia do livro. Felizmente a primeira edição do livro está disponível de graça neste link, a página 32 à 34 (ou da 46 à 48 do PDF).

Agora que já temos uma ideia do método, podemos consolidar estes conceitos com um artigo com mais exemplos práticos.

*Artigo: Artigo de Pesquisa Binária do TopCoder

Um artigo que inclui mais exemplos e uma explicação diferente

Passemos à prática com um problema simples, mas que ilustra bem o método:

Problema 1: Tavas and Karafs

Problema C da ronda 299 (Div. 2) do CodeForces - Tavas and Karafs

Opcionalmente, podem também tentar o próximo problema, que é um pouco mais complicado, mas depois de verem onde podem aplicar pesquisa binária torna-se fácil.

*Problema 2: Read Time

Problema C da ronda 200 (Div. 1) do CodeForces - Read Time

Aplicações contínuas

Se em vez de considerarmos uma lista discreta de elementos, podemos considerar, analogamente, uma lista "contínua". A ideia será semelhante, mas com o objetivo de obter um certo elemento de uma função monótona contínua até uma certa precisão.

Os artigos da secção anterior já cobriram parcialmente este tema, mas vejamos um artigo mais focado.

Artigo: Artigo da Wikipedia do método das bisseções

Um artigo exatamente sobre esta secção, cujo método é conhecido como "método das bisseções".

Para finalizar a secção, um problema a acompanhar:

Problema 3: Vanya and Lanterns

Problema B da ronda 280 (Div. 2) do CodeForces - Vanya and Lanterns

Intuição

Depois destes vários exemplos, temos algumas notas a fazer. A primeira, é que este método normalmente se aplica a problemas cujo objetivo seja encontrar o valor mínimo ou máximo tal que uma determinada condição se verifica. Assim, transformamos um problema de minimizar ou maximizar, num problema de decisão (cuja resposta será "sim" ou "não"). Isto permite resolver problemas que seriam aparentemente complexos pensando na sua versão de decisão em vez da versão de otimização.