Fast search algorithms for look‐up tables

Abstract

Various parameter values are provided in the form of data tables, where data keys are ordered and unevenly spaced in general, for real‐time simulation of dynamic systems. However, most parameter values required for simulation do not explicitly exist in data tables. Thus, unit intervals, including parameter values, are searched rather than the data keys. Since real‐time constraint enforces use of a fixed step size in integration of system differential equations because of the inherent nature of input from and output to real hardware, the worst case of iterated probes in searching algorithms is the core measure for comparison. The worst case is expressed as Big O. In this study, conventional bisection, interpolation, and fast searches are analyzed and compared in Big O as well as the newly developed searching algorithms: modified fast search and modified regular falsi search. If the criterion is actual execution time required for searching, most numerical tests in this paper show that bisection search is superior to the others. Interpolation search and its variations show better performance in the case of linear or near linear data distribution than bisection search. The numerical tests show that modified regular falsi search is faster than the other interpolation searches in either expected time or worst cases. Given parameter tables should be carefully examined for their data distribution in order to determine the most appropriate searching algorithm for the application.

Citation

Yoon, S. and Kang, H. (2003), "Fast search algorithms for look‐up tables", Engineering Computations, Vol. 20 No. 3, pp. 238-247. https://doi.org/10.1108/02644400310467180