Searching a NSArray for the nearest number(s)

Is there an easy way to search an NSArray of numbers to find the nearest (or exact if it exists) matches to a user-input number?

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

The program returns the three nearest values in descending order of closeness: 4, 7, 2, and most importantly gives the NSArray index of the t开发者_JAVA技巧hree objects: 2, 0, 5.

Update: see below for a better solution than my first one.

Here's a solution using NSDictionary wrappers for each number and its index, with sorting using a comparator block. It probably doesn't scale very well, but it gets the job done.

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 a C array of indexes, eliminating the need for NSDictionary wrappers

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

Sort the existing array of values "indirectly", using an array of indexes, and sorting by the "distance" to the search value. The first three items after the sort are the "nearest" 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;
}

The naive method would be to search the source array for 5, increment the found count and store the appropriate information if found, then search for 4 and 6, etc.

A second method would be to keep a sorted copy of the source array: 2, 4, 7, 11, 18, 23

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

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

If the left neighbor wins, store its info, then compare its left neighbor with the original greater-than-five number:

(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)

You should only need to do three comparisons in this case, and you'll need to decide whether you want to use < or <=. Your second array is just n*ptr size, so it's not a huge space growth.

Is this a homework question? An easy way to code this by utilizing apis is to generate an array called distances containing the distance from each original number, create a sorted version of that array called sorted, then to search distances for the lowest three numbers in sorted to get the index from which you can look up the original number.

Tested Code: 100 % works

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

OUTPUT:

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

ResultArray is : ( 4, 7, 2 )

indexArray is : (

    "<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)]"

        )