Find in Library

Searching over a sorted list is a classical problem in computer science. Binary Search takes at most <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mfenced open="⌊" close="⌋" separators="|"><mrow><mrow><mrow><msub><mrow><mi mathvariant="normal">log</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow><mo>⁡</mo><mrow><mi>n</mi></mrow></mrow></mrow></mfenced><mo>+</mo><mn>1</mn></mrow></semantics></math></inline-formula> tries to find an item in a sorted list of size <i>n</i>. Interpolation Search achieves an average time complexity of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">O</mi><mo>(</mo><mrow><mrow><mi mathvariant="normal">log</mi></mrow><mo>⁡</mo><mrow><mrow><mrow><mi mathvariant="normal">log</mi></mrow><mo>⁡</mo><mrow><mi>n</mi></mrow></mrow></mrow></mrow><mo>)</mo></mrow></semantics></math></inline-formula> for uniformly distributed data. Hybrids of Binary Search and Interpolation Search are also available to handle data with unknown distributions. This paper analyzes the computation cost of these methods and shows that interpolation can significantly affect their performance—accordingly, a new method, Interpolation Once Binary Search (IOBS), is proposed. The experimental results show that IOBS outperforms the hybrids of Binary Search and Interpolation Search for nonuniformly distributed data.