Title

Analysis Of Recursive Batched Interpolation Search

Keywords

analysis of algorithms; Batched searching; binary search; D.4.3; F.2.2; interpolation search

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 be O(m loglog (2 n/m) +m), where n is the size of the file and m 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. © 1990 BIT Foundations.

Publication Date

3-1-1990

Publication Title

BIT

Volume

30

Issue

1

Number of Pages

42-50

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/BF01932130

Socpus ID

34249952636 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/34249952636

This document is currently not available here.

Share

COinS