Алгоритм или структура данных, которая находит «ближайшего соседа» целого числа в очень большом наборе

Question

У меня чрезвычайно большой набор натуральных чисел, x.

x имеет приблизительно 10 000 членов.

У меня также есть случайное число, n.

I sh, чтобы найти алгоритм или структуру данных f, которая эффективно находит / индексирует ближайшее число ниже n в наборе x. Из-за большого размера набора временная сложность имеет значение , и лучше, чем o (n), идеально.

Пример:

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

Имеет ли такой алгоритм или структура данных существует?

Answer 1

Двоичный поиск - это типичный алгоритм, используемый для задач такого типа.

Пример реализации:

    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;
    }