ISSN:
1572-9125
Keywords:
D.4.3
;
F.2.2
;
Batched searching
;
binary search
;
interpolation search
;
analysis of algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01932130
Permalink
