Fuzzy NSDictionary - use nearest key

Question

I have a list of around 4000 numbers e.g: {10, 20, 30, 40, 50,...}

Each number is a key in an NSDictionary, so I can fetch the object associated with a number, e.g.

[NSDictionary objectForKey:[NSNumber numberWithInt:20];

However if the key is not in the dictionary, I'd like to find the nearest key (assuming there is a meaningful relationship between values, in my example, 10>20>30 etc).

So e.g.

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

Or is there another data structure that would be more appropriate for doing this? I'd thought of using a sorted NSArray, where the key would be the array index, then if object was null keep incrementing the array pointer until the object is found, however this would result in a sparsly populated array with 999,999 elements :)

Thanks

Answer 1

Essentially you need to keep a sorted list (NSMutableArray) of keys. To find a key use the indexOfObject:inSortedRange:options:usingComparator: method of NSArray passing in NSBinarySearchingInsertionIndex as the options which will perform a binary search giving you an index even if it doesnt find the exact element. You'll have to fetch both keys yourself and compare them.