Computação · Busca binária
Como achar um nome entre um milhão em 20 passos?
O que você vai ver
Uma lista telefônica tem um milhão de nomes, em ordem alfabética. Conferir um por um poderia levar um milhão de olhadas. Dá para fazer melhor? Abra bem no meio. O nome que você procura vem depois, então a primeira metade inteira some. Sobra meio milhão. Abra o meio do que restou e corte ao meio de novo. E de novo. Cada olhada joga fora metade do que resta. Vinte metades levam um milhão até um, porque dois elevado a vinte é pouco mais de um milhão. Um bilhão de nomes? Só mais dez olhadas.
