Algorithm or data structure that finds "nearest neighbor" of integer in a very large set

Question

I have an extremely large set of positive integers, x.

x has approximately 10,000 members.

I also have a random number, n.

I wish to find an algorithm or data structure f that efficiently finds/indexes the nearest number below n in the set x. Due to the large size of the set, time complexity matters and anything better than o(n) is ideal.

Example:

x = [0, 500, 765]
n = 632
f(x, n) == 500

Does such an algorithm or data structure exist?

Answer 1

Binary Search is the typical algorithm used for this type of problem.

Sample implementation:

    static int FindBelowOrEqualIndex(int[] a, int key)
    // assumes that 'a' is sorted in ascending order
    {
        int left = 0;
        int right = a.Length - 1;

        while (left <= right)
        {
            int median = (left + right) / 2;

            if (a[median] == key)                
                return median;                

            if (key < a[median])
            {
                right = median - 1;
            }
            else
            {
                left = median + 1;
            }
        }
        return left - 1;
    }