Dividir para conquistar: quebrar, resolver e juntar

Quebrar o problema em metades

No curso intermediário a recursão apareceu como uma função que chama a si mesma até bater num caso base. Isso é a mecânica. Dividir para conquistar é uma forma poderosa de usar essa mecânica: em vez de encolher o problema de um em um, você o corta ao meio. Procurar um nome numa lista telefônica ordenada é o exemplo perfeito. Você não lê nome por nome do começo. Abre no meio, vê se o nome procurado vem antes ou depois, e joga fora metade da lista de uma vez. Sobra a metade que interessa, e você repete o corte. Cada passo descarta cinquenta por cento do que restava, então até uma lista de um milhão de nomes é vencida em cerca de vinte olhadas.

A técnica tem sempre três fases. Primeiro dividir: partir o problema em subproblemas menores, quase sempre em duas metades. Depois resolver cada metade, o que costuma ser a própria função se chamando de novo, até os pedaços ficarem tão pequenos que a resposta é óbvia (uma lista de um item já está ordenada, uma busca em zero elementos não achou nada). Por fim combinar: reunir as respostas parciais na resposta do problema inteiro. Na busca binária a combinação é trivial, porque você segue só uma das metades. Em outros algoritmos, como você verá, juntar é justamente onde o algoritmo ganha ou perde a eficiência.

A parte esquecida é juntar

É fácil se encantar com a divisão e esquecer a combinação, mas ela é o coração da técnica. Pense em ordenar uma lista de cartas embaralhadas com o merge sort. Dividir é simples: corte a pilha ao meio, e ao meio de novo, até sobrarem pilhas de uma carta só, que já estão em ordem por definição. Aí começa o trabalho de verdade: pegar duas pilhinhas já ordenadas e intercalar carta a carta, comparando os topos, para formar uma pilha maior ordenada. Repita subindo até reconstruir a lista inteira em ordem. A divisão não custa quase nada; é a intercalação, feita em todos os níveis, que ordena de fato. Por isso a fase de combinar merece atenção: ela costuma esconder a lógica que faz o algoritmo funcionar.

// busca binária: dividir para conquistar em ação
FUNÇÃO busca(lista, alvo, ini, fim)
  SE ini > fim ENTÃO
    RETORNE -1        // caso base: intervalo vazio, não achou
  FIM
  meio <- (ini + fim) / 2
  SE lista[meio] = alvo ENTÃO
    RETORNE meio      // achou
  SENÃO SE alvo < lista[meio] ENTÃO
    RETORNE busca(lista, alvo, ini, meio - 1)   // metade da esquerda
  SENÃO
    RETORNE busca(lista, alvo, meio + 1, fim)   // metade da direita
  FIM
FIM

A cada chamada, a busca descarta metade do intervalo. Aqui a combinação é seguir só uma metade, então é imediata.

Onde a técnica brilha

Dividir para conquistar não serve para tudo. Ela compensa quando o problema pode ser partido em pedaços independentes do mesmo tipo e quando juntar as respostas é mais barato do que resolver tudo de uma vez. Ordenar, buscar em dados ordenados, multiplicar números gigantes e várias tarefas de geometria seguem esse molde. Já somar todos os itens de uma lista não ganha nada em dividir: um laço simples resolve com o mesmo esforço. A pergunta a fazer é honesta: quebrar ao meio e recombinar realmente reduz o trabalho, ou só adiciona a papelada das metades sem benefício? Quando a resposta é que reduz, a técnica transforma problemas lentos em rápidos.