FastBinarySearch is a powerful library designed for high-performance searching in sorted arrays of floating point numbers. Originating from a research article published in the Journal of Parallel and Distributed Computing, this library showcases fast, vectorizable algorithms that significantly enhance search efficiency.

This library features multiple variants of algorithms, including well-known methods such as binary search, lower_bound (as implemented in the STL), and innovative search techniques like ternary, pentary, and nonary, culminating in a groundbreaking new search method with a complexity of O(1). The algorithms are tailored to efficiently determine the insertion point within a sorted vector, making the library ideal for applications in numerical methods, spline interpolation, and empirical distribution calculations.

Key Features:

• Fast and Vectorizable Algorithms: Designed specifically for sorted floating point arrays, these algorithms utilize modern CPU parallel capabilities, enabling rapid searches.
• Header-only Library: This makes integration simple and requires minimal setup. Just include BinSearch.h, instantiate an engine, and start searching!
• Robust Examples: The library includes examples demonstrating both scalar and vectorial search methods, showcasing its versatility:

  using namespace BinSearch;
  const uint32_t nx = 5;
  const double x[nx] = { 1, 2, 4, 5, 9 };
  // Construct bin search algorithm
  BinAlgo<SSE, double, Ternary> searcher(x, n);
  // Scalar search for the point xi=2.5
  uint32_t j = searcher.scalar(2.5);
  // Vectorial search for multiple points
  const uint32_t m = 8;
  const double xi[m] = { 1, 2, 4, 5, 1.5, 2.5, 4.8, 8.2 };
  uint32_t ji[m];
  searcher.vectorial(xi, ji, m);
  

• Cross-Language APIs: Simple APIs in C and Fortran are available, enhancing compatibility and potential integration into established libraries like NAG.

Performance Insights:

The FastBinarySearch library boasts impressive throughput metrics, outperforming traditional searching algorithms. Benchmark tests conducted on Intel Xeon CPUs indicate performance improvements of up to two orders of magnitude over conventional binary search methods in various scenarios. The detail of these benchmarks, including throughput rates, further emphasizes the library's capabilities.

Testing reflects the efficacy of different algorithms that adapt to single and double precision searches in both scalar and vectorial modes.

Learn More:

For further information, you can delve into the original research paper available on Elsevier or access a preprint draft on arXiv. If you encounter any questions or require assistance in implementing this library, feel free to reach out!