A PERFORMANCE MEASUREMENT BETWEEN TRADITIONAL BINARY SEARCH AND BUIATTI BINARY SEARCH ALGORITHMS

Abstract

This undergraduate research project presents a detailed performance measurement comparing the traditional binary search algorithm with Buiatti binary search, an innovative adaptive variation. Although traditional binary search is worst-case optimal for comparisons (complexity O(log n)), its fixed symmetric splitting strategy does not exploit statistical properties of the data distribution or access patterns that could reduce the average search cost. In practical scenarios where data exhibits non-uniform distributions (such as clusters) or where repetitive access patterns exist, this independence from the data represents a missed optimization opportunity. In this context, Buiatti binary search emerges as a promising alternative, designed to optimize the average case by introducing local verification heuristics before classical splitting. The methodology adopted, based on classic works such as Cormen et al. (2009) and Knuth (1998), consisted of the implementation and comparative analysis of both versions. Empirical tests using random search strategies and control points revealed that, although both maintain logarithmic complexity, the Buiatti approach offers measurable performance gains and greater stability in reference locality scenarios, validating its potential for specific applications.