Vou assumir que você está usando alguma forma de array e tenha acesso a ele, mesmo que isto seja apenas a representação interna. Caso contrário não vejo como fazer sequer uma busca simples.
Isto pode depender um pouco da linguagem que você está usando. A linguagem precisa ter como descobrir se um índice é válido ou não. O problema é que, até onde eu sei, sempre que você não sabe a quantidade de itens, você também não sabe quando o índice é inválido. Então eu diria que é impossível.
Se conseguir esta informação, você pode ir olhando cada item dobrando o índice se o que está procurando é maior que o valor encontrado naquele índice e vendo se ele ainda é válido ou não (capturando uma exceção ou outra forma que a linguagem permita). Se o o que você procura for menor do que o valor do item encontrado, aí você pega a metade do item atual e o último verificado e não precisa mais se preocupar em verificar se o item é válido. Se já achou um menor, então quando tiver que olhar para um maior deverá considerar a metade entre este item e o maior anteriormente encontrado.
Outra forma é achar o tamanho antes fazendo justamente busca binária. Pode usar a mesma técnica ou fazer a busca binária clássica considerando que o tamanho imaginário seria 2 elevado a 32. É o processo inverso, sempre que der erro vai dividindo o índice por 2, sempre que não der erro pega a metade. Quando não der erro tenta a metade entre esse que não deu erro e o último. Com o tamanho você faz busca binária tradicional.
Sinceramente, embora eu não possa provar, acho que isto é um falso problema justamente pelo requisito de saber quando o índice estoura. Em uma estrutura de dados/linguagem (qualquer array ou tipos que usam array em sua implementação em Java, C#, etc.) que pode informar se estourou o limite, o tamanho está disponível e é só perguntar. Em C, se o programador tem como saber o tamanho quando monta um array ou outra estrutura baseada nele. O que pode acontecer é o código ignorar propositalmente o tamanho. Pra que fazer isto? Se o fizer, acho impossível resolver. Em C, se você jogar fora o tamanho do array, você não saberá se acessou um lugar que não devia.
Claro que pode ter maneiras específicas de obter isto se o valor possuir um padrão que seja garantido que não será confundido com outra coisa e ver se ainda está na área do array. Mesmo isso, acredito que não dá para garantir isto.
Fora isto, demonstre a real necessidade. Mostre como faria a busca simples neste caso para ver se conseguimos transformar em busca binária.