Interpolated binary search: An efficient hybrid search algorithm on ordered datasets
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 interp...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2021-10-01
|
| Series: | Engineering Science and Technology, an International Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S221509862100046X |
| _version_ | 1818437663357665280 |
|---|---|
| author | Adnan Saher Mohammed Şahin Emrah Amrahov Fatih V. Çelebi |
| author_facet | Adnan Saher Mohammed Şahin Emrah Amrahov Fatih V. Çelebi |
| author_sort | Adnan Saher Mohammed |
| collection | DOAJ |
| description | 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 datasets that change dynamically and produce a dynamic distribution. Experimental results show that IBS performs better compared to other algorithms that use a similar approach. |
| first_indexed | 2024-12-14T17:28:15Z |
| format | Article |
| id | doaj.art-9e0f627ae30d4b1f9dbb5efdeb47e5a1 |
| institution | Directory Open Access Journal |
| issn | 2215-0986 |
| language | English |
| last_indexed | 2024-12-14T17:28:15Z |
| publishDate | 2021-10-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Engineering Science and Technology, an International Journal |
| spelling | doaj.art-9e0f627ae30d4b1f9dbb5efdeb47e5a12022-12-21T22:53:10ZengElsevierEngineering Science and Technology, an International Journal2215-09862021-10-0124510721079Interpolated binary search: An efficient hybrid search algorithm on ordered datasetsAdnan Saher Mohammed0Şahin Emrah Amrahov1Fatih V. Çelebi2Karabuk University, Faculty of Engineering, Computer Engineering Dept., Karabuk, Turkey; Corresponding author.Ankara University, Faculty of Engineering, Computer Engineering Dept., Ankara, TurkeyAnkara Yıldırım Beyazıt University, Faculty of Engineering and Natural Sciences, Computer Engineering Dept., Ankara, TurkeyThe 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 datasets that change dynamically and produce a dynamic distribution. Experimental results show that IBS performs better compared to other algorithms that use a similar approach.http://www.sciencedirect.com/science/article/pii/S221509862100046XBinary searchInterpolation searchHybrid searchAdaptive searchInterpolation binary search |
| spellingShingle | Adnan Saher Mohammed Şahin Emrah Amrahov Fatih V. Çelebi Interpolated binary search: An efficient hybrid search algorithm on ordered datasets Engineering Science and Technology, an International Journal Binary search Interpolation search Hybrid search Adaptive search Interpolation binary search |
| title | Interpolated binary search: An efficient hybrid search algorithm on ordered datasets |
| title_full | Interpolated binary search: An efficient hybrid search algorithm on ordered datasets |
| title_fullStr | Interpolated binary search: An efficient hybrid search algorithm on ordered datasets |
| title_full_unstemmed | Interpolated binary search: An efficient hybrid search algorithm on ordered datasets |
| title_short | Interpolated binary search: An efficient hybrid search algorithm on ordered datasets |
| title_sort | interpolated binary search an efficient hybrid search algorithm on ordered datasets |
| topic | Binary search Interpolation search Hybrid search Adaptive search Interpolation binary search |
| url | http://www.sciencedirect.com/science/article/pii/S221509862100046X |
| work_keys_str_mv | AT adnansahermohammed interpolatedbinarysearchanefficienthybridsearchalgorithmonordereddatasets AT sahinemrahamrahov interpolatedbinarysearchanefficienthybridsearchalgorithmonordereddatasets AT fatihvcelebi interpolatedbinarysearchanefficienthybridsearchalgorithmonordereddatasets |