We devise a theoretical model for dichotomic search algorithms for constrained optimization. We show that, within our model,
a certain way of choosing the breaking point minimizes both expected as well as worst case performance in a skewed binary
search. Furthermore, we show that our protocol is optimal in the expected and in the worst case. Experimental results illustrate
performance gains when our protocols are used within the search strategy by Streeter and Smith.
This work was supported by the National Science Foundation through the Career: Cornflower Project (award number 0644113).
We would like to express our thanks to three anonymous reviewers for their helpful comments as well as John Hughes, Anna Lysyanskaya,
Claire Mathieu, Steven Smith, and Mathew Streeter for supporting this work and some very insightful discussions.