Searching for the first item satisfying property with penalty for every test The problem in terms of a step function on integers: A step function of integers is $0$ until $s$ (the "item" in question) and then $1$. That is, $s$ is the first integer that satisfies the property $f(s) = 1$. The only way to find out the function's value $f(x)$ is to run a test to evaluate it, where each test has a penalty $p(x)$. Given a range $[a,b]$ in which the step is known to occur, find the stepping point $s$ with minimal total penalty.

In the case I'm interested in, $p(x) = x$.

If $p(x)$ is just a constant, then binary search is the solution (I think?).

Background: There is a process that takes X minutes before a certain event occurs, always at the same time, but this time is unknown. I need to find this time. To check, start the process, wait X minutes and then run a test to find out if the event happened or not. After testing, the process restarts (so you can't just test every minute to find out the minimum time). 

Edit: I forgot to mention that for simplicity's sake the distribution of $s$ is uniform in $[a,b]$, that is $P(x=s, x \in [a,b]) = 1/(b-a+1)$. A more realistic distribution in my actual problem is monotonically increasing, for example $P(x) = 2x/(b-a+1)^2$. 



Update: usul's answer (with a minor tweak) describes how to calculate the value which needs minimizing, which is the expected cost given a penalty function and the probability distribution of the target value. 

The question still stands: which algorithm actually minimizes that value in the case $p(x)=x$ and the two distributions discussed above (uniform and increasing)? More generally - what's an algorithm that takes the penalty function and always yields the minimum expected cost?
Here is a writeup following up on Tsuyoshi's pointer to use DP.

Given $p(x)$, we can write any (decent, deterministic) algorithm as a binary decision tree with nodes weighted by $p(x)$. The root of the tree is the first node the algorithm selects to test; the left child of each $x$ is the next node to test if $f(x)$ is zero and the right node is the next to test if $f(x) = 1$.

An algorithm's worst-case performance on weights $p(x)$ is its weighted depth: the maximum over any path to a leaf of the sum of the path's weights.

Therefore the optimal deterministic algorithm minimizes this value.

The "minimum maximum length" or "cost" of a path starting at node $x$ is $p(x)$ plus the cost of the tree on the nodes remaining to be searched. The nodes remaining to be searched will always be an interval. This gives the DP relation:


  $cost[x, z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( cost[x, y-1], cost[y, z]) \right)$


with $cost[x,x] = 0$ as a base case (except $cost[b,b] = p(b)$ unless you are promised that a $1$ occurs in the interval).



(Update)

With a probability distribution, say you want to minimize total expected cost. The expected cost for searching an interval is the cost of searching the first node $y$, plus the expected cost for searching the remainder. Using $\Pr[a,b|c,d]$ for the conditional probability of being in interval [a,b] given that we're in interval [c,d], this gives the following:


  $cost[x,z] = \min_{y \in [x,z-1]} \left(p(y) + \Pr[x,y-1|x,z] cost[x,y-1] + \Pr[y,z|x,z] cost[y,z] \right)$ .




Here's what I had before, which does something ... let's say "different" instead of "wrong."

It minimizes maximum expected cost. The idea is, given an algorithm, consider the node $y$ with highest expected cost $\Pr[y] p(y)$. We want the algorithm that minimizes this value. We might view this as risk-averse, I suppose.


  $cost[x,z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( \Pr[x,y-1 | x,z] cost[x,y-1],  \Pr[y,z | x,z] cost[y,z]) \right)$.