Search in an Ordered Array Having Variable Probe Cost
William J. Knight · SIAM Journal on Computing · 1988
Steiglitz and Parks [“What Is the Filter-Design Problem?,” Proc. 1986 Princeton Conference on Information Science and Systems, B. W. Dickenson, ed., Princeton University, Dept. of Electrical Engineering, Princeton, NJ, 1986] have shown that a problem in filter design gives rise to a related problem of how to search an ordered array in which the cost of a probe into the array varies with the location being probed. In this paper we prove that if probing in location k has cost $k^p $, where p is a positive integer, then the expected cost of a successful or unsuccessful search for a target element is at least $(p + 1)^{ - 1} n^p \lg n + O(n^p )$. We also prove the somewhat surprising fact that ordinary binary search has this expected cost. However, for the case $p = 1$ we describe what appears to be a marginally better search algorithm.