Interpolation Once Binary Search over a Sorted List

Jun-Lin Lin ()
Additional contact information
Jun-Lin Lin: Department of Information Management, Yuan Ze University, Taoyuan 32003, Taiwan

Mathematics, 2024, vol. 12, issue 9, 1-12

Abstract: Searching over a sorted list is a classical problem in computer science. Binary Search takes at most log 2 ⁡ n + 1 tries to find an item in a sorted list of size n . Interpolation Search achieves an average time complexity of O ( log ⁡ log ⁡ n ) 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.

Keywords: binary search; interpolation search; interpolated binary search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/9/1394/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/9/1394/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:9:p:1394-:d:1387956

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().