O poder dos dados ordenados

A lista telefônica e o dicionário de papel

Imagine procurar o nome Silva numa lista telefônica antiga com um milhão de nomes. Você não começava no primeiro e ia conferindo um por um, isso levaria uma vida. Você abria o catálogo mais ou menos no meio, via que caiu na letra M, e na hora sabia uma coisa poderosa: Silva vem depois de M, então toda a primeira metade do catálogo, de A a M, pode ser ignorada. Você acabou de descartar quinhentos mil nomes com um único olhar. Repetindo o gesto, abre a metade que sobrou, cai em T, sabe que Silva vem antes, e descarta outra fatia enorme. Em pouquíssimas aberturas você chega no nome. Esse superpoder tem um único responsável: os nomes estavam em ordem alfabética.

É essa a informação escondida na ordem. Numa lista embaralhada, olhar um item no meio não diz nada sobre onde o alvo está: ele pode estar de qualquer lado, então você não pode descartar nada e é obrigado a conferir tudo. Numa lista ordenada, olhar o item do meio diz tudo: se o alvo é menor que ele, está do lado de baixo; se é maior, está do lado de cima. Uma única comparação divide o problema ao meio e joga fora metade dos candidatos com segurança total. Ordem transforma cada comparação de um passo minúsculo (descartei um item) num passo gigante (descartei metade). Guardar isso é entender por que ordenar dados, embora custe trabalho, costuma valer muito a pena.

Saber onde NÃO procurar

Vale insistir nessa mudança de perspectiva, porque é o coração da busca eficiente. Numa busca comum, você foca em onde o alvo pode estar. Com dados ordenados, o pulo do gato é saber onde o alvo NÃO pode estar, e eliminar essa região de uma vez. Cada comparação bem escolhida não avança um passo, ela corta o campo de busca pela metade. É a diferença entre procurar uma pessoa numa multidão perguntando um por um e usar a informação de que a multidão está organizada por altura: uma pergunta sobre o meio já elimina metade das pessoas. Essa capacidade de descartar em bloco, e não de avançar item a item, é o que separa uma busca lenta de uma busca relâmpago.

Ordenar é um investimento

Se a ordem é tão poderosa, por que nem sempre os dados estão ordenados? Porque ordenar custa trabalho, e esse custo precisa valer a pena. Manter uma coleção sempre em ordem exige esforço a cada inserção, e ordenar uma bagunça de uma vez também consome tempo, assunto do próximo módulo. A conta é simples: se você vai buscar poucas vezes numa lista, a busca linear resolve e ordenar seria desperdício. Mas se você vai consultar a mesma coleção milhares de vezes, ordenar uma vez e depois usar busca binária em todas as consultas é um investimento que se paga com folga. É a lógica de afiar o machado antes de cortar muitas árvores: o tempo gasto afiando volta multiplicado. Entender esse equilíbrio entre o custo de ordenar e o ganho de buscar rápido é maturidade de programador.