I don't really see what you mean ("3 segments" suggests asking for f(1/3) and f(2/3) to me, but that's not enough data to know anything). I'll type what I thoug

I don't really see what you mean ("3 segments" suggests asking for f(1/3) and f(2/3) to me, but that's not enough data to know anything). I'll type what I thought, which may be the same thing. If a < b < c, f(a) <= f(b) and f(b) >= f(c) then a <= m <= c; choosing e.g. 1/4, 1/2 and 3/4 [EDIT: was 1/3, 1/2, 2/3, which is not optimal - see reply by jacobolus] allows you to find out in which 1/2 [EDIT: was 1/3] of the range you should look with three measurements. You could recurse on the above, e.g. by measuring 1/4 + 1/8 and 1/4 + 3/8 if 1/4 <= m <= 3/4 [EDIT: match above corrections.] Another interesting trick is measuring 1/2 + epsilon, which (almost) bisects the range with only two measurements. [EDIT^2: removed "(with negligible probability of m being in [1/2, 1/2 + epsilon] - we just hope that doesn't happen, so this doesn't work for adversarial input!). [EDIT: this actually works pretty well for non-adversarial input.]"]. [EDIT^2: I should've paid a bit more attention when writing this, thanks for the (many) corrections jacobolus!]