Interpolated binary search: An efficient hybrid search algorithm on ordered datasets
Küçük Resim Yok
Tarih
2021
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier - Division Reed Elsevier India Pvt Ltd
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
The exponential increase in the rate of data size is much higher than the increase in the speed of the computer, which has given much focus to search algorithms in the research literature. Finding an item in an ordered dataset is an efficient method in the data processing. However, binary and interpolation algorithms are commonly used to search ordered datasets in many applications. In this paper, we propose a hybrid algorithm for searching ordered datasets based on the idea of interpolation and binary search. The proposed algorithm is called Interpolated Binary Search (IBS). It is well known that the performance of traditional interpolation search depends specifically on key distribution, and its performance degrades significantly in non-uniform distributed datasets. Therefore, our proposed algorithm works efficiently on various distribution datasets. In particular, IBS aims to search datasets of unknown distribution or data sets that change dynamically and produce a dynamic distribution. Experimental results show that IBS performs better compared to other algorithms that use a similar approach. (C) 2021 Karabuk University. Publishing services by Elsevier B.V.
Açıklama
Anahtar Kelimeler
Binary search, Interpolation search, Hybrid search, Adaptive search, Interpolation binary search
Kaynak
Engineering Science and Technology-An International Journal-Jestech
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
24
Sayı
5
