Comparative Analysis of Binary and Interpolation Search Algorithms on Integer Data Using C Programming Language

To perform data search, there are various algorithms that have been developed, such as binary search and interpolation search. There are various views on these two algorithms, regarding which one is better than the other. From the various views that have emerged, this study aims to find out which algorithm is more efficient in terms of time complexity and memory complexity using Big-O notation, as well as its execution time in the C programming language. This research was conducted with 6 datasets consisting of 3 datasets with uniform data types and 3 datasets with non-uniform data types. Each dataset type consists of 1 million, 10 million, and 100 million data. The results show that the binary search algorithm is more efficient to use rather than interpolation search on datasets that are not uniformly distributed or the data type is unknown. While the interpolation search algorithm is more efficient to use rather than binary search on datasets that are known to be uniformly distributed.

I. Introduction

In the present, the usage of efficient algorithms is an important factor in software implementation because it can affect the speed and memory usage of software. One of the most frequently used algorithms in software implementation is the search algorithm. Search algorithm itself is a type of algorithm that allows taking certain items from a set of items [1]–[3]. There are many methods to implement search algorithms and some of the most popular are binary search and interpolation search.