Fast and Vectorizable Alternatives to Binary Search

Given an array X of N+1 strictly ordered floating point numbers and an array Z of M floating point numbers belonging to the interval [X[0],X[N]), a common problem in numerical methods algorithms is to find the indices of the largest numbers in the array X which are smaller or equal than the numbers in the array Z. The general solution to this problem is the well known "binary search" algorithm, which has complexity O(M log2 N). This paper describes improvements to the binary search algorithm, which are faster and vectorizable (SIMD-friendly). Next it proposes a new vectorizable algorithm based on a indexing technique, which reduces complexity of search operations to O(M). Some benchmark test results using SSE2 instructions demonstrate that with N=1025 the proposed algorithm is about 26 times faster than the classical binary search in single precision and 15 times faster in double precision.