# Find last zero in infinite stream of 0's followed by 1's

Given an infinite stream with the property, such that after all 0's there are only all 1's, find the index of the last 0.

I'm looking for code review, best practices, optimizations etc. Verifying complexity to be O (log n) where n is the first 1 encountered in the search (not the first 1 in the stream).

/**
* An infinite list takes in an the number of zeros'.
* After those many zero's only 1's are followed.
* This is a hypothetical class to represent a inifinite stream in real world.
* like lets assume a linkedlist shared my multiple threads which keep appending 1's
*/
class InfiniteList extends ArrayList<Integer> {

InfiniteList(int zeroCount) {
super(zeroCount);
}

private void add (int zeroEnd) {
for (int  i = 0; i < zeroEnd; i++) {
}
}

@Override
public Integer get(int i) {
return super.size() <= i ? 1 : super.get(i);
}

@Override
public int size() {
throw new UnsupportedOperationException("The array size cannot be obtained.");
}
}

public final class FindZeroEndInInfiniteStream {

private FindZeroEndInInfiniteStream() {}

/**
* Takes in a infinite list, such that after stream of all 0's we encounter only all 1's.
* Returns the last index of zero.
* If no zero is found then -1 is returned.
* This code would block until a zero is found in an infinite stream.
* If the infinite has 0's and 1's mixed randomly then output is unpredicatable/
*
* @param infinite      the infinite stream of 0's followed by 1's
* @return              the last index of zero.
*/
public static int zeroLastIndex(InfiniteList infinite) {
if (infinite == null) throw new NullPointerException("The inifinte array was null");
return modifiedBinarySearch(infinite);
}

private static int modifiedBinarySearch(InfiniteList infinite) {
if (infinite.get(0) == 1) return -1;
if (infinite.get(1) == 1) return 0;

int passive = 0;  // does nothing, simply stores previous lower bound.
int active = 1; // does the searching, toggling back and forth

while(!(infinite.get(active) == 0 && infinite.get(active + 1) == 1)) {
if (infinite.get(active) == 0) {
passive = active;
active = active * 2;
} else {
active = (passive + active)/2; // active has gone beyond the 38th parallel :). Now go back to south korea.
}
}
return active;
}

public static void main(String[] args) {
InfiniteList iList = new InfiniteList(15);
Assert.assertEquals(14,  zeroLastIndex(iList));

iList = new InfiniteList(27);
Assert.assertEquals(26,  zeroLastIndex(iList));
}
}


• And here I was thinking: How on earth to make an infinite stream? Is a good old InputStream / OutputStream considered infinite? I have to agree though that a class that extends ArrayList is not an infinite stream. – Simon Forsberg Feb 21 '14 at 23:32
• @SimonAndréForsberg Another way to represent it would be something like Iterable<Boolean>. – svick Feb 21 '14 at 23:46