Поиска ближайшего элемента в множестве целых чисел

Question

Я следующая задача решить:

Дан N целых чисел, образующие множества S и другие целое число A (не neccesarily же, как любой из N целых чисел, приведенных), найти целое число от множества S ближайший к целому A.

Сначала я думал, что это проблема NNS (поиск ближайшего соседа), но в NNS целое число A также должно быть из множества S, что в моем случае не обязательно должно быть ,

Затем я подумал о том, чтобы поместить каждое целое из S в двоичное дерево поиска и искать первое вхождение, когда один из детей меньше, чем запрос, а родительский - больше, чем запрос, но я не знаю, будет ли это работать.

Какую структуру данных я должен использовать? Спасибо.

EDIT: забыл упомянуть, что мне нужно, чтобы это было лучше, чем O (n), O (logn) - достаточно хорошо. Таким образом, я не могу использовать линейный поиск.

Answer 1

Ваша проблема - типичный ввод для двоичного поиска в отсортированном массиве/списке. Единственная трудность заключается в том, чтобы знать четыре случая (см. Их мою реализацию C#). Двоичный поиск часто можно найти как часть стандартной библиотеки, в C# случае

https://msdn.microsoft.com/en-us/library/y15ef976(v=vs.110).aspx

private static int Closest(int[] S, int A) { 
    int index = Array.BinarySearch(S, A); 

    if (index >= 0) 
    return S[index];  // exact match, A in S 
    else if (index == -1) 
    return S[0];   // A is less than any item in S 
    else if (index < -S.Length) 
    return S[S.Length - 1]; // A is greater than any item in S 
    else {     // A is in [left..right] range 
    // C# specific range encoding; consult your languages/library manual 
    int left = ~index - 1; 
    int right = ~index; 

    if (Math.Abs(S[left] - A) < Math.Abs(S[right] - A)) 
     return S[left]; 
    else 
     return S[right]; 
    } 

Тесты:

int[] array = new[] { 10, 20, 30, 40, 50 }; 

    // 10 
    Console.Write(Closest(array, 11)); 
    // 20 
    Console.Write(Closest(array, 19)); 
    // 10 
    Console.Write(Closest(array, 4)); 
    // 50 
    Console.Write(Closest(array, 400)); 
    // 30 
    Console.Write(Closest(array, 30)); 

Answer 2

Если набор отсортирован, вы можете легко изменить бинарный поиск, чтобы найти ближайшее целое число в O(log n). Вы можете себе представить, что вы ищете место в наборе, где положить номер, чтобы он остался отсортированным. Как только вы нашли его с бинарным поиском (на C++ вы можете использовать lower_bound для этого), вы просто проверяете, какой номер ближе - тот, который был до или после.

Answer 3

Поскольку список уже отсортирован, лечить как проблема размещения нового элемента в списке, поддерживающего порядок сортировки. После того, как местоположение (скажем, i-я позиция) завершено, вычислите дельта от S [i-1] и S [i + 1], чтобы получить ближайшее целое число до A.