 Solution

Use binary search: maintain the interval of possible integers and ask whether $n$ is at least the first integer in its upper half. Each answer reduces the number of possibilities to at most its previous number divided by two, rounded up. After $q$ questions at most $\lceil 10^6/2^q\rceil$ possibilities remain. Since $2^{20}=1048576>10^6$, twenty questions suffice.

A yes/no decision tree of depth twenty has at most $2^{20}$ leaves, whereas the possible finishing orders number $15!=1307674368000$. Thus twenty questions cannot identify the finishing order of fifteen horses, assuming no ties. With unrestricted yes/no questions, the exact minimum for $n$ horses is $\lceil {\log }_2(n!)\rceil$: the leaf count is a lower bound, and repeatedly partitioning the remaining permutations into two nearly equal sets attains it. In particular fifteen horses require 41 questions.

By Stirling's formula,so the leading number of questions is $n{\log }_{2}n$. These questions may ask about whole sets of possible orders; restricting them to pairwise comparisons is a different model.