Optimal average-case binary search with outcome-dependent costs

We consider the problem of identifying an unknown number in the set [n]={1,…,n}, by asking queries of the form: “Is the unknown number greater than j ∈ [n]?” If the answer to the query is Yes , the algorithm incurs an integer cost α ≥ 0, if the answer to the query is No , the algorithm incurs an integer cost β ≥ 0. The search algorithm must satisfy the hard constraint that it never incurs a cost greater than an input parameter D , for any possible sequence of queries. We present several scenarios in which this problem naturally arises. Assuming that the search space [n] is endowed with a probability distribution p=(p1,…,pn), where pi is the probability that the unknown element is i ∈ [n], we design an O (n 2 D)-time Dynamic Programming algorithm to construct an optimal search procedure, that is, a search algorithm that requires a minimum expected number of queries and satisfies the aforementioned hard constraint.