DouKaku?

求める数の個数 n なのに 時間計算量 O(log n) というのがよく判らないんです。
素人考えだと、最低 O(n)はかかるような気がするんですけど、解説をお願いできますでしょうか