Searching a sorted array of floating point numbers

Question

Is there an optimized function in any numerical library (MKL, Boost, GSL,..etc) that searches a sorted array of floating point numbers for the closest match to a given float? Another function which will solve the same problem for me will generate a random sample from a custom discrete probability distribution.

Answer 1

Wrapping comments (of me & @betabandido) into an answer:

You basically need to find 2 candidates, the closest "upper" element, and the closest "lower" element (assuming the element is not in the list). This can be achieved using Binary Search efficiently (O(logN))

By using std::lower_bound() you can get the higher element, and the lower is the element before it in the array.

Compare the two candidates - the one which is closest to the given float is your answer.