Let $D$ be the set of integers from $1$ to $n$ inclusive for $n \geq 1$, and let $$f(i) = \begin{cases} 0& i \leq k \\ i - k& i > k \end{cases}\,\,\,\forall\, i \in D$$ for some $k \in D$. That is, $f$ is a discrete unit ramp starting at some value $k$.
Suppose the value of $k$ is unknown a priori, but is distributed over $D$ with probability $p(k)$, and we wish to find $k$. To do this, we can query the value of $f(i)$ for as many values of $i$ as needed, but there are two "quirks":
the cost of querying the value of $f(i)$ is $i$ (that is, the cost of a query is proportional to the index being queried)
since $f$ is a unit ramp, any query where $i > k$ will give us the value of $k$
The total cost is the sum of all queries needed to identify $k$.
My two questions are:
Is there a known optimal algorithm for minimizing the expected total cost given uniform $p(k)$?
Is there a known optimal algorithm for minimizing the expected total cost given an arbitrary $p(k)$?
This problem has cropped up in a software routine I'm writing. I'd appreciate any advice or assistance.