Módulo Pesquisa Binária

Neste módulo iremos explorar a técnica de pesquisa binária e os seus variados usos. Este módulo está dividido em quatro artigos, que exploram conceitos diferentes, incrementalmente.

É importante mencionar que a pesquisa binária pode ser aplicada de muitas formas, muitas vezes não é nada óbvio como o fazer. O primeiro é muito introdutório e podem-no ignorar a não ser que nunca tenham visto nada parecido com pesquisa binária. O último artigo é opcional e apenas o devem explorar se tiverem algum tempo.

Artigo: Introdução a pesquisa em listas

Este artigo é uma introdução ao conceito base de pesquisa binária. Como tal, a maior parte já deve conhecer estes conceitos e nesse caso não vale a pena perder tempo a resolvê-los.

Artigo: Pesquisa binária

Neste artigo têm uma introdução ao "poder real" da pesquisa binária. Poderão ver várias aplicações diferentes e ganhar alguma intuição de como verificar se a podem usar num determinado problema.

Artigo: Divide and Conquer

A técnica de "Divide and Conquer" (ou dividir para conquistar) é a ideia por trás da pesquisa binária. Neste artigo generalizamos o conceito e vemos algumas aplicações.

*Artigo: Ternary Search

O nome deste artigo é um pouco enganador. O objetivo da pesquisa ternária não é apenas generalizar o conceito de pesquisa binária, mas sim um método que permite determinar o máximo/mínimo de uma função bitónica em tempo logarítmico. É útil em vários tipos de problemas.

Com estes três artigos (ou quatro se leram o opcional) já devem ter uma boa ideia do que é e para que serve a pesquisa binária. Para os que estão a ver isto pela primeira vez, podem reparar que um problema recente tinha um formato onde seria fácil aplicar pesquisa binária para a solução para 100, nomeadamente o problema B da final deste ano, No Fundo do Mar, conseguem ver como?

Problemas de consolidação

Este conjunto de problemas é constituído por alguns problemas extra um pouco mais difíceis, mas que resumem bem a maioria dos tópicos dos artigos.

Nota: A fonte dos problemas representa a plataforma de submissão (todos são submetiveis) e não o concurso onde apareceu.

Os últimos dois problemas são um pouco mais complicados e, por isso, se não tiverem uma ideia de como os resolver, consultem os editoriais.