Search NSArray for the nearest number (s)

Question

Is there an easy way to search for NSArray numbers to find the closest (or exact, if one exists) match to the user input number?

Let's say I have an array like this: 7, 23, 4, 11, 18, 2 , and the user enters 5 .

The program returns the three closest values ​​in descending order of proximity: 4, 7, 2 and most importantly gives the NSArray index for three objects: 2, 0, 5 .

Answer 1

Update: see below a better solution than the first.

Here is a solution using NSDictionary wrappers for each number and its index, sorted using a comparator block. It probably doesn't scale very well, but it does its job.

 static NSString *const kValueKey = @"value"; static NSString *const kIndexKey = @"index"; + (void)searchArray:(NSArray *)array forClosestValuesTo:(int)value resultValues:(NSArray **)values resultIndexes:(NSArray **)indexes { NSMutableArray *searchObjs = [NSMutableArray arrayWithCapacity:[array count]]; [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { [searchObjs addObject:[NSDictionary dictionaryWithObjectsAndKeys:obj, kValueKey, [NSNumber numberWithUnsignedInt:idx], kIndexKey, nil]]; }]; [searchObjs sortUsingComparator:^NSComparisonResult(id obj1, id obj2) { NSUInteger d1 = ABS([[obj1 objectForKey:kValueKey] intValue] - value); NSUInteger d2 = ABS([[obj2 objectForKey:kValueKey] intValue] - value); if (d1 == d2) { return NSOrderedSame; } if (d1 < d2) { return NSOrderedAscending; } return NSOrderedDescending; }]; NSArray *results = [searchObjs subarrayWithRange:NSMakeRange(0, 3)]; if (values) { *values = [results valueForKey:kValueKey]; } if (indexes) { *indexes = [results valueForKey:kIndexKey]; } } 

Update: here's an updated solution that sorts an array of C indices, eliminating the need for an NSDictionary wrapper

 static NSString *const kValueKey = @"value"; static NSString *const kArrayKey = @"array"; int CSCompareIndexes(void *data, const void *value1, const void *value2) { NSDictionary *dict = (NSDictionary *)data; NSArray *array = [dict objectForKey:kArrayKey]; int valueToFind = [[dict objectForKey:kValueKey] intValue]; int index1 = *(int *)value1; int index2 = *(int *)value2; NSNumber *num1 = [array objectAtIndex:index1]; NSNumber *num2 = [array objectAtIndex:index2]; return ABS([num1 intValue] - valueToFind) - ABS([num2 intValue] - valueToFind); } void CSSearchNumberArray(NSArray *array, int valueToFind, NSArray **resultValues, NSArray **resultIndexes) { NSInteger numValues = [array count]; NSUInteger *indexes = malloc(sizeof(NSUInteger) * numValues); assert(indexes); int i; for (i = 0; i < numValues; i++) { indexes[i] = i; } NSDictionary *data = [NSDictionary dictionaryWithObjectsAndKeys:array, kArrayKey, [NSNumber numberWithInt:valueToFind], kValueKey, nil]; qsort_r(indexes, numValues, sizeof(NSUInteger), (void *)data, CSCompareIndexes); NSMutableArray *tmpValues = [NSMutableArray arrayWithCapacity:3], *tmpIndexes = [NSMutableArray arrayWithCapacity:3]; for (i = 0; i < 3; i++) { [tmpValues addObject:[array objectAtIndex:indexes[i]]]; [tmpIndexes addObject:[NSNumber numberWithInt:indexes[i]]]; } if (resultValues) { *resultValues = [NSArray arrayWithArray:tmpValues]; } if (resultIndexes) { *resultIndexes = [NSArray arrayWithArray:tmpIndexes]; } free(indexes); } int main (int argc, char *argv[]) { NSAutoreleasePool *pool = [NSAutoreleasePool new]; NSMutableArray *test = [NSMutableArray array]; int i; for (i = 0; i < 10; i++) { [test addObject:[NSNumber numberWithInt:(arc4random() % 100)]]; } NSLog(@"Searching: %@", test); NSArray *values, *indexes; CSSearchNumberArray(test, 50, &values, &indexes); NSLog(@"Values: %@", values); NSLog(@"Indexes: %@", indexes); [pool drain]; return 0; } 

Answer 2

Sort an existing array of values ​​"indirectly", use an array of indexes and sort by "distance" to the search value. The first three elements after sorting are the "closest" values.

Example:

 #import <Foundation/Foundation.h> @interface NearestSearcher : NSObject { } + (NSArray *) searchNearestValuesOf: (int) value inArray: (NSArray *) values; @end @implementation NearestSearcher + (NSArray *) searchNearestValuesOf: (int) value inArray: (NSArray *) values { // set up values for indexes array NSMutableArray *indexes = [NSMutableArray arrayWithCapacity: values.count]; for (int i = 0; i < values.count; i++) [indexes addObject: [NSNumber numberWithInt: i]]; // sort indexes [indexes sortUsingComparator: ^NSComparisonResult(id obj1, id obj2) { int num1 = abs([[values objectAtIndex: [obj1 intValue]] intValue] - value); int num2 = abs([[values objectAtIndex: [obj2 intValue]] intValue] - value); return (num1 < num2) ? NSOrderedAscending : (num1 > num2) ? NSOrderedDescending : NSOrderedSame; }]; return [indexes subarrayWithRange: NSMakeRange(0, 3)]; } @end // DEMO #define NUM_VALUES 20 int main (int argc, const char * argv[]) { NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; // DEMO SETUP // set up values array with random values NSMutableArray *values = [NSMutableArray arrayWithCapacity: NUM_VALUES]; for (int i = 0; i < NUM_VALUES; i++) [values addObject: [NSNumber numberWithInt: arc4random() % 200]]; // display values array for (int i = 0; i < values.count; i++) NSLog(@"%2d: %4d", i, [[values objectAtIndex: i] intValue]); // get a random value for x int x = arc4random() % 200; // METHOD INVOCATION NSArray *results = [NearestSearcher searchNearestValuesOf: x inArray: values]; // SHOW RESULTS NSLog(@"------------------------"); NSLog(@"x: %d", x); for (NSNumber *num in results) NSLog(@"%@: %@", num, [values objectAtIndex: [num intValue]]); [pool drain]; return 0; } 

Answer 3

The naive method is to search for the source array for 5 , increment the found account and save the relevant information if it is found, then search 4 and 6 , etc.

The second way would be to save a sorted copy of the original array: 2, 4, 7, 11, 18, 23

then use -indexOfObjectPassingTest: to find the first number greater than 5 in this array, then compare this number with your left neighbor to see which is closer to 5 :

(7-5) < (5-4) ? storeinfo(7) : storeinfo(4)

If the left neighbor wins, save its information, then compare its left neighbor with the original number of more than five:

(7-5) < (5-2) ? storeinfo(7) : storeinfo(2)

But if the right side wins, compare its right neighbor with the loser:

(11-5) < (5-2) ? storeinfo(11) : storeinfo(2)

In this case, you only need to make three comparisons, and you will need to decide whether you want to use < or <= . Your second array is just the size of n * ptr, so this is not a huge increase in space.

Answer 4

Is this a homework question? An easy way to encode this with apis is to create an array called distances containing the distance from each source number, create a sorted version of this array named sorted , then search distances for the lowest three numbers in sorted to get an index from which you can look source number.

Answer 5

Tested code: 100% working

 NSMutableArray *arrayWithNumbers=[[NSMutableArray alloc]initWithObjects:[NSNumber numberWithInt:7],[NSNumber numberWithInt:23],[NSNumber numberWithInt:4],[NSNumber numberWithInt:11],[NSNumber numberWithInt:18],[NSNumber numberWithInt:2],nil]; NSLog(@"arrayWithNumbers : %@ \n\n",arrayWithNumbers); NSMutableArray *ResultArray = [ [ NSMutableArray alloc] init]; NSMutableArray *lowestArray = [ [ NSMutableArray alloc] init]; NSMutableArray *tempArray = [ [ NSMutableArray alloc] init]; NSMutableArray *indexArray = [ [ NSMutableArray alloc] init]; NSNumber *numberToFind=[NSNumber numberWithInt:5]; int limitToFilter = 3; for (NSNumber *number in arrayWithNumbers) { int a=[number intValue]-[numberToFind intValue]; [lowestArray addObject:[NSNumber numberWithInt:abs(a)]]; } tempArray=[lowestArray mutableCopy]; NSSortDescriptor *LowestTohighest = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES]; [lowestArray sortUsingDescriptors:[NSArray arrayWithObject:LowestTohighest]]; int upto = limitToFilter-[ResultArray count]; for (int i = 0; i < upto; i++) { [lowestArray objectAtIndex:i]; if ([tempArray containsObject:[lowestArray objectAtIndex:i]]) { NSUInteger index=[tempArray indexOfObject:[lowestArray objectAtIndex:i]]; [ResultArray addObject:[arrayWithNumbers objectAtIndex:index]]; [indexArray addObject:[NSIndexSet indexSetWithIndex:index]]; } } NSLog(@"ResultArray is : %@ \n\n",ResultArray); NSLog(@"indexArray is : %@ \n\n",indexArray); //here release all 4 arrays if u dont need them 

CONCLUSION:

arrayWithNumbers: (7, 23, 4, 11, 18, 2)

ResultArray: (4, 7, 2)

indexArray: (

  "<NSIndexSet: 0x4e06620>[number of indexes: 1 (in 1 ranges), indexes: (2)]", "<NSIndexSet: 0x4e04030>[number of indexes: 1 (in 1 ranges), indexes: (0)]", "<NSIndexSet: 0x4e06280>[number of indexes: 1 (in 1 ranges), indexes: (5)]" )