Dima TС учетом большого числа дырок, лично мне кажется оптимальный алгоритм - сначала поиск интервала с дыркой от единицы вверх, затем поиск непрерывного вниз двоичным поиском.
т.е. берем 1 - сканируем весь поток, затем 2,4,8 и т.д.
как получили дырку - продолжаем между предыдущим и текущим, т.е. дальше чистый двоичный поиск.
вероятность что нет первого составляет 10^3 к 1, нет второго 10^6 к 1 и т.д. (если теорию вероятностей правильно помню), т.е. скорее всего за один проход все найдется. В худшем случае 40 сканов для непрерывной последовательности в миллион. Т.е. тут сложность O(log2(n) + log2(n)) но по сравнению с чистым двоичным поиском высока вероятность решить в один проход. Двоичным от миллиона поиск значения 1 потребует 20 проходов.

Также получается универсально, т.к. тут нет ограничения сверху, т.е. без разницы сколько значений хоть миллион, хоть олимпиард :)
а что мешает объединить два этих метода ? пусть будет бинарный поиск с нижним расширением :-)

Dima T,
ну в бинарном поиске ты всё равно весь файл читаешь
что мешает вести
L,R бинарного поиска
и попутно считать число значений меньше L+степени двойки

чтение из файла ведь всё равно затратнее

Dima T,

задача олимпиадная, проверяют такие вещи самыми неудобными наборами