Find 1s in almost all 0 array using comparisons only

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python):

def compare(i, j):
    comparisons.append((i, j))
    if data[i] == data[j]:
        return 0 
    else:
        return 1 if data[i] > data[j] else -1

Using this function, we must find all three 1s with using at most 73 comparisons. We must output the compared pairs as a tuple as well as the coordinates of the three 1s.

Now, I tried writing a code with the following logic:

And I thought that maybe because two 1s will use 2 instead of 3 comparisons, it might come down do 73. This was not only long to code (I am studying mathematics, not CS), but I wrote to my prof, and he said this wouldn't work, and that I should try dynamic programming. I'm a bit lost, as I've never solved a coding program that is this limiting, so I have an other idea, which is to do a first parse of the array, going in pairs, so comparing (data[0], data1),(data[2], data[3]),.... This way, no matter how the 1s are placed, I ought to find at least one of them. I would also store all of the results of these comparisons, and then cross-check them with a set of new comparisons, namely (data1,data[2]),(data[5],data[6]),...

Any help is appreciated, specific code would be most useful, so I can understand how such a method would work.

Edit:
I almost have it now thanks to @orlp, but I don't see why I still get 75 comparisons:

```
comparisons = []

def compare(i, j):
comparisons.append((i, j))
if data[i] == data[j]:
return 0 
else:
return 1 if data[i] > data[j] else -1

def find_ones(data):
found_ones = []

for i in range(0, len(data), 2):
if compare(i, i + 1) != 0:
found_ones.append(i if data[i] == 1 else i + 1)
if len(found_ones) == 3:
return comparisons, found_ones[0], found_ones[1], found_ones[2]

remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]
for i

Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be a 0).

Now there are two cases after these 50 comparisons: either we've found all three 1's, or we've found one 1, because the remaining two were part of the same pair. In the latter case we must find the pair which contains the last two 1's.

In this case there will be 49 pairs left (we can exclude the (0, 1) pair we identified earlier) one of which is the (1, 1) pair. We can find it by pairing the pairs, and doing one comparison each (for a total of 24 comparisons, leaving one pair out). This will identify which pair is the one with (1, 1), or if not, we know it must be the last pair.

This gives a total of 74 comparions. In fact, we could have saved one more comparison in the first step by stopping after 49 comparisons. If we have found two 1's in those first 49 comparisons we do one more to find the last 1 and we are done, and if we've found only one 1 it's useless to perform the comparison on the last pair, as it could only be (0, 0) or (1, 1), giving us no information.

StackExchange Computer Science Q#166885, answer score: 13