Fuzzy NSDictionary - использовать ближайший ключ

Question

У меня есть список из примерно 4000 номеров, например: {10, 20, 30, 40, 50,...}

Каждое число является ключом в NSDictionary, поэтому я могу выбрать объект, связанный с числом, например,

[NSDictionary objectForKey:[NSNumber numberWithInt:20];

Однако, если ключ отсутствует в словаре, я бы хотел найти ближайший ключ (при условии, что между значениями существует значимая связь, в моем примере 10> 20> 30 и т. Д.).

Так, например

[NSDictionary objectForKey:[NSNumberWithInt:19]] would return the value for key:20.

Или есть другая структура данных, которая была бы более подходящей для этого? Я подумал об использовании отсортированного NSArray, где ключом будет индекс массива, тогда, если объект был нулевым, продолжайте увеличивать указатель массива до тех пор, пока объект не будет найден, однако это приведет к малонаселенному массиву с 999 999 элементами:)

Спасибо

Answer 1

По сути вам нужно сохранить отсортированный список (NSMutableArray) ключей.Чтобы найти ключ, используйте метод indexOfObject:inSortedRange:options:usingComparator: NSArray, передавая NSBinarySearchingInsertionIndex в качестве параметров, которые будут выполнять двоичный поиск, давая вам индекс, даже если он не находит точный элемент.Вам придется самим взять оба ключа и сравнить их.

Answer 2

Если ваш список чисел находится в порядке возрастания, вы можете выполнить двоичный поиск в массиве. Поэтому при поиске ключа x вы должны начать с индекса array.length / 2, сравнить ключ в этой позиции с x и продолжить с левой частью, если она больше x, или с правой частью, если она меньше x , Продолжайте, пока не найдете ближайший ключ к x.

Это очень быстро (в вашем случае для журнала (4000) ~ 12 поисков в массиве) и не требует дополнительного хранилища.