  Given an array $X$ of $N+1$ strictly ordered floating point numbers and a
floating point number $z$ in the interval $[X_0,X_N)$, a common problem is to
find the index $i$ of the interval $[X_{i},X_{i+1})$ containing $z$. This
problem arises for instance in the context of spline interpolation or the
computation of empirical probability distribution from empirical data. Often it
needs to be solved for a large number of different values $z$ and the same
array $X$, which makes it worth investing resources upfront in pre-processing
the array $X$ with the goal of speeding up subsequent search operations. In
some cases the values $z$ to be processed are known simultaneously in blocks of
size $M$, which offers the opportunity to solve the problem vectorially,
exploiting the parallel capabilities of modern CPUs. The common solution is to
sequentially invoke $M$ times the well known binary search algorithm, which has
complexity $O(log_2 N)$ per individual search and, in its classic formulation,
is not vectorizable, i.e. is not SIMD friendly. This paper describes technical
improvements to the binary search algorithm, which make it faster and
vectorizable. Next it proposes a new vectorizable algorithm, based on an
indexing technique, applicable to a wide family of $X$ partitions, which solves
the problem with complexity $O(1)$ per individual search at the cost of
introducing an initial overhead to compute the index and requiring extra memory
for its storage. Test results using streaming SIMD extensions compare the
performance of the algorithm versus various benchmarks and demonstrate its
effectiveness. Depending on the test case, the algorithm can produce a
throughput up to two orders of magnitude larger than the classic binary search.
Applicability limitations and cache-friendliness related aspects are also
discussed.
