Comment by hobos_delight

I don't think you can do better than a binary search here, so log2(1000000) questions, which happens to come out to 20 with rounding.

I tried thinking a bit outside the box for other questions that would break down the search space - but none of them were any improvement on the binary search.