Efficient algorithm for binary search enhancement

Abstract

Binary search algorithms suffer from inefficiencies such as starvation and search of non-essential space leading to a runtime of O(log n). This paper presents an Enhanced Binary Search algorithm that ensures that search is performed if and only if the search key is within the feasible search space; thus exhibiting a better time complexity than the Binary Search algorithm - in particular, when the search key is outside the feasible region of the list. The Enhanced algorithm is implemented by contrasting the average runtimes of the Enhanced Binary Search algorithm against the Binary Search algorithm for different input sizes. The waterfall research methodology was adopted and result analysis shows that the Enhanced Binary Search algorithm exhibits a runtime of O(1) than the Binary Search algorithm when the search key is outside the feasible search region of the list, therefore enabling search to be performed in reduced time.

Keywords: algorithm, search, search space, time complexity, space complexity.