Isto é oproblema descrito emProgramming pearls. Eu não consigo entender o método de busca binária descrito pelo autor. Alguém pode ajudar a elaborar? Obrigado.

EDIT: Eu posso entender a pesquisa binária em geral. Eu simplesmente não consigo entender como aplicar a pesquisa binária neste caso especial. Como decidir se o número que falta está dentro ou não em algum intervalo para que possamos escolher outro. Inglês não é minha língua nativa, essa é uma das razões pelas quais não consigo entender bem o autor. Então, use inglês simples por favor :)

EDIT: Obrigado a todos por sua grande resposta e comentários! A lição mais importante que eu inclinei de resolver esta questão éPesquisa binária aplica-se não apenas à matriz ordenada!