Is there a known optimal solution for searching an ordered list with non-uniform query cost? 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.
 A: It sounds like your "quirks" are based on a linear search.
Use a Binary search.
If k is ANY value where i > k, then why query i+n recursively starting with n=0 until k > 1? Since it's an already  ordered list you don't need to treat it like a series dependent on it's previous recursion. Why not just query the last element in the list? if it's not there then k doesn't exist?
If it is an ordered series and not an ordered list, then you're pretty much out of luck. That's just the nature of a series.
If it is a list, did you mean to say that k is the value of the smallest i where the value k is greater than it's index i?
In that case you don't have to go i+1 one by one until  your "k > i" condition returns true, do a binary search, use threads, or do both. Binary search is well documented, been around almost 100 years at least, so I'm not going to explain it here.
Using threads to speed it up should be intuitive if you know how to use some kind of parallel for or for each, nice linear speedup, but if not there are some good examples, probably even either some build in functors or templates or lambda functions in w/e language you're using.
It's just a linear speedup, time*cpu_cores plus maybe some benefit from using virtual cores or hyper threads, so it may or may not be that important to you especially if the machine has no idle cores to use, is often doing other critical work or w/e.
