A busca binária encontra um limite em O(log n) passos, descartando metade do que sobra a cada vez. Funciona sempre que uma pergunta de sim ou não é falsa até certo ponto e verdadeira depois. “Este horário é pelo menos o alvo?” em uma lista ordenada é uma dessas perguntas. “Um caminhão com esta carga consegue terminar a tempo?” é outra, sobre cargas em vez de posições.
Escolha uma convenção de intervalo e mantenha-a. Aqui a resposta fica no intervalo semiaberto [left, right), com right começando no tamanho da lista para que “depois do fim” seja uma resposta válida. Se o meio não puder ser a resposta, mova left para depois dele; se puder, posicione right nele. O laço termina quando os dois se encontram.
Teste os limites de propósito: uma lista vazia, um alvo abaixo ou acima de tudo, sequências de valores iguais e, em Java, mid * mid ou left + right estourando um int.