A Fibonacci Version of Kraft’s Inequality Applied to Discrete Unimodal Search
Arthur S. Goldstein, Edward M. Reingold · SIAM Journal on Computing · 1993
A function is unimodal if it strictly increases to a unique maximum and then strictly decreases. The problem of determining the smallest possible interval containing the maximum of a unimodal function, by probing only at integer values is studied. In the finite case, the search takes place over the range 0 to N, while in the infinite case the search takes place over the nonnegative integers. The analyses are based on an unusual Fibonacci version of Kraft’s inequality.