caa a22 4500 465820921 CHVBK 20180323112135.0 cr unu---uuuuu 170327e19900301xx s 000 0 eng 10.1007/BF01932130 doi (NATIONALLICENCE)springer-10.1007/BF01932130 Lang S. Department of Computer Science, University of Central Florida, 32816, Orlando, FL, USA aut Analysis of recursive batched interpolation search [Elektronische Daten] [S. Lang] For an ordered file of records with uniformly distributed key values, we examine an existing batched searching algorithm based on recursive use of interpolation searches. The algorithm, called Recursive Batched Interpolation Search (RBIS) in this paper, uses a divide-and-conquer technique for batched searching. The expected-case complexity of the algorithm is shown to beO(m loglog (2n/m) +m), wheren is the size of the file andm is the size of the query batch. Simulations are performed to demonstrate the savings of batched searching using RBIS. Also, simulations are performed to compare alternative batched searching algorithms which are based on either interpolation search or binary search. When the file's key values are uniformly distributed, the simulation results confirm that interpolation-search based algorithms are superior to binary-search based algorithms. However, when the file's key values are not uniformly distributed, a straight-forward batched interpolation search deteriorates quickly as the batch size increases, but algorithm RBIS still outperforms binary-search based algorithms when the batch size passes a threshold value. BIT Foundations, 1990 D.4.3 nationallicence F.2.2 nationallicence Batched searching nationallicence binary search nationallicence interpolation search nationallicence analysis of algorithms nationallicence BIT Numerical Mathematics Kluwer Academic Publishers 30/1(1990-03-01), 42-50 0006-3835 30:1<42 1990 30 10543 https://doi.org/10.1007/BF01932130 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01932130 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Lang S. Department of Computer Science, University of Central Florida, 32816, Orlando, FL, USA aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Kluwer Academic Publishers 30/1(1990-03-01), 42-50 0006-3835 30:1<42 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer