Find a positive integer within range using only elementary operations
My first thought was to try a binary search but was stumped because I can't use floor/ceil.

I'm not sure why you thought that would matter.  Once you have a maximum number, all you need is to divide the difference between max and min in half and add it to min on each iteration.  Here's a simple example that works for your test case.  It might need tweaking for some edge cases.
const int MAX_SECRET = 400000;
public static decimal Find()
{
    decimal max = MAX_SECRET;
    decimal min = 0;
    while(max - min &gt; 0)
    {
        decimal temp = ((max - min) / 2) + min;
        if(BlackBox(temp,&quot;==&quot;))
        {
            return temp;
        }
        if(BlackBox(temp, &quot;&lt;&quot;))
        {
            max = temp;
        }
        else
        {
            min = temp;
        }
    }
    return max;
}

EDIT
Did some more thinking on the efficiency of this algorithm.  The problem mainly stems from using a decimal to represent an int.  A decimal doesn't want to do integer math.  One way around this is, to use the rounding functionality when the maximum precision is exceeded, to make a floor function.  This greatly reduces the iterations to find the target number.
Here's one way that uses the max precision of C#:
const int MAX_SECRET = 400000;
public static decimal Find()
{
    decimal max = MAX_SECRET;
    decimal min = 0;
    decimal count = 0;
    while(max - min &gt; 0)
    {
        decimal temp = floor((max - min) / 2) + min;
        if(BlackBox(temp,&quot;==&quot;))
        {
            return temp;
        }
        if(BlackBox(temp, &quot;&lt;&quot;))
        {
            max = temp;
        }
        else
        {
            min = temp;
        }
    }
    return max;
}
const decimal MAX_PRECISION = 10000000000000000000000000000M;
static decimal floor(decimal num)
{
    decimal temp = (num / MAX_PRECISION) * MAX_PRECISION;
    if(temp &gt; num)
    {
        --temp;
    }
    return temp;
}

This cuts the iterations down to the same level as using int's instead of decimal's.  To use this in a different language the MAX_PRECISION constant may need to adjusted.