Binary search Cocoa NSArray

BinarySearchTC.m

//
//  BinarySearchTC.m
//
//  Created by Marcus Rohrmoser on 12.01.10.
//  Copyright 2009 Marcus Rohrmoser mobile Software. All rights reserved.
//

#define USE_APPLICATION_UNIT_TEST 0

#import <SenTestingKit/SenTestingKit.h>

@interface BinarySearchTC : SenTestCase {}
@end

#import "MroBinarySearch.h"

@implementation BinarySearchTC

-(void)testBinarySearchUsingSelector
{
    STAssertEquals(NSOrderedAscending, [@"0" compare:@"05"], @"");
    STAssertEquals(NSOrderedAscending, [@"05" compare:@"1"], @"");
    STAssertEquals(NSOrderedAscending, (NSComparisonResult)[@"0" performSelector:@selector(compare:) withObject:@"05"], @"");
    STAssertEquals(NSOrderedAscending, (NSComparisonResult)[@"05" performSelector:@selector(compare:) withObject:@"1"], @"");

    NSArray *a = [NSArray arrayWithObjects:@"0", @"1", @"2", @"3", @"4", nil];
    STAssertEquals(0, [a binarySearch:@"0"], @"0");
    STAssertEquals(1, [a binarySearch:@"1"], @"1");
    STAssertEquals(4, [a binarySearch:@"4"], @"4");
    STAssertEquals(-2, [a binarySearch:@"05"], @"05");
    STAssertEquals(-3, [a  binarySearch:@"1" usingSelector:nil inRange:NSMakeRange(2, a.count-2)], @"1");
}


NSInteger stringSort(id str1, id str2, void *context)
{
//    NSLogD(@"a:%@, b:%@", str1, str2);
    return [str1 compare:str2];
}


-(void)testBinarySearchUsingFunction
{
    STAssertEquals(NSOrderedAscending, stringSort(@"0", @"05", NULL), @"");
    STAssertEquals(NSOrderedAscending, stringSort(@"05", @"1", NULL), @"");

    NSArray *a = [NSArray arrayWithObjects:@"0", @"1", @"2", @"3", @"4", nil];
    STAssertEquals(0, [a binarySearch:@"0" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(1, [a binarySearch:@"1" usingFunction:stringSort context:NULL], @"1");
    STAssertEquals(4, [a binarySearch:@"4" usingFunction:stringSort context:NULL], @"4");
    STAssertEquals(-3, [a binarySearch:@"1" usingFunction:stringSort context:NULL inRange:NSMakeRange(2, a.count-2)], @"1");
    STAssertEquals(-2, [a binarySearch:@"05" usingFunction:stringSort context:NULL], @"05");

    a = [[NSArray arrayWithObjects:@"aa", @"ab", @"bb", @"bc", @"ca", @"cb", nil] sortedArrayUsingSelector:@selector(compare:)];
    STAssertEquals(-3, [a binarySearch:@"b" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(2, -(-3) - 1, @"");
    STAssertEquals(-5, [a binarySearch:@"bz" usingFunction:stringSort context:NULL], @"0");

    a = [NSArray array];
    STAssertEquals(-1, [a binarySearch:@"a" usingFunction:stringSort context:NULL], @"0");

    a = [NSArray arrayWithObjects:@"b", nil];
    STAssertEquals(-1, [a binarySearch:@"a" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(0, [a binarySearch:@"b" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(-2, [a binarySearch:@"c" usingFunction:stringSort context:NULL], @"0");

    a = [NSArray arrayWithObjects:@"b", @"d", nil];
    STAssertEquals(-1, [a binarySearch:@"a" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(0, [a binarySearch:@"b" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(-2, [a binarySearch:@"c" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(1, [a binarySearch:@"d" usingFunction:stringSort context:NULL], @"0");
    STAssertEquals(-3, [a binarySearch:@"e" usingFunction:stringSort context:NULL], @"0");
}


-(void)testBinarySearchUsingDescriptors
{

    NSArray *a = [NSArray arrayWithObjects:@"0", @"4", @"1", @"3", @"2", nil];
    NSSortDescriptor *tmp = [[NSSortDescriptor alloc] initWithKey:@"self" ascending:YES];
    NSArray *sort = [NSArray arrayWithObject:tmp];
    a = [a sortedArrayUsingDescriptors:sort];

    STAssertEquals(NSOrderedAscending, [tmp compareObject:@"0" toObject:@"05"], @"");
    STAssertEquals(NSOrderedAscending, [tmp compareObject:@"05" toObject:@"1"], @"");
    [tmp release];

    STAssertEquals(0, [a binarySearch:@"0" usingDescriptors:sort], @"0");
    STAssertEquals(1, [a binarySearch:@"1" usingDescriptors:sort], @"1");
    STAssertEquals(4, [a binarySearch:@"4" usingDescriptors:sort], @"4");
    STAssertEquals(-2, [a binarySearch:@"05" usingDescriptors:sort], @"05");
    STAssertEquals(-3, [a  binarySearch:@"1" usingDescriptors:sort inRange:NSMakeRange(2, a.count-2)], @"1");
}

@end

MroBinarySearch.h

//
//  MroBinarySearch.h
//
//  Created by Marcus Rohrmoser on 12.01.10.
//  Copyright 2010 Marcus Rohrmoser mobile Software. All rights reserved.
//

#if 0
// No Logging
#define NSLogD(x,...)                             /* NSLog(x,##__VA_ARGS__) */
#else
// Do Logging
#define NSLogD(x,...) NSLog(x,##__VA_ARGS__)
#endif

/** Add binary search capabilities to NSArray.
 *
 * A port from http://www.jcurl.org/m2/site/jc-core/0.7-SNAPSHOT/apidocs/org/jcurl/math/CurveCombined.html#binarySearch(double[],%20int,%20int,%20double)
 * with the author's friendly permission.
 *
 */
@interface NSArray(MroBinarySearch)

-(NSInteger)binarySearch:(id)key;

/**
 * @see MroBinarySearch::binarySearch:
 * @see NSArray::sortedArrayUsingSelector:
 */
-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator;

/**
 * Binary search a part of an array.
 *
 * @param key nil returns -1
 * @param comparator may be nil to use @selector(compare:)
 * @param range
 * @return found index.
 *
 * @see MroBinarySearch::binarySearch:
 * @see NSArray::sortedArrayUsingSelector:
 */
-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator inRange:(NSRange)range;

/**
 * @see MroBinarySearch::binarySearch:
 * @see NSArray::sortedArrayUsingFunction:context:
 */
-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context;

/**
 * @see MroBinarySearch::binarySearch:
 * @see NSArray::sortedArrayUsingFunction:context:
 */
-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range;

/**
 * @see MroBinarySearch::binarySearch:
 * @see NSArray::sortedArrayUsingDescriptors:
 */
-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors;

-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors inRange:(NSRange)range;

@end

MroBinarySearch.m

//
//  MroBinarySearch.m
//
//  Created by Marcus Rohrmoser on 12.01.10.
//  Copyright 2010 Marcus Rohrmoser mobile Software. All rights reserved.
//

#import "MroBinarySearch.h"

@implementation NSArray(MroBinarySearch)

#pragma mark Using Selector

-(NSInteger)binarySearch:(id)key
{
    return [self binarySearch:key usingSelector:nil];
}


-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator
{
    return [self binarySearch:key usingSelector:comparator inRange:NSMakeRange(0, self.count)];
}


-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator inRange:(NSRange)range
{
    NSLogD(@"[NSArray(MroBinarySearch) binarySearch:%@ usingSelector:]", key);
    if (self.count == 0 || key == nil)
        return -1;
    if(comparator == nil)
        comparator = @selector(compare:);

//	check overflow?
    NSInteger min = range.location;
    NSInteger max = range.location + range.length - 1;

    while (min <= max)
    {
    	// http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
        const NSInteger mid = min + (max - min) / 2;
        switch ((NSComparisonResult)[key performSelector:comparator withObject:[self objectAtIndex:mid]])
        {
            case NSOrderedSame:
                return mid;
            case NSOrderedDescending:
                min = mid + 1;
                break;
            case NSOrderedAscending:
                max = mid - 1;
                break;
        }
    }
    return -(min + 1);
}


#pragma mark Using C-Function

-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context
{
    return [self binarySearch:key usingFunction:comparator context:context inRange:NSMakeRange(0, self.count)];
}


-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range
{
    NSLogD(@"[NSArray(MroBinarySearch) binarySearch:%@ usingFunction:]", key);
    if(self.count == 0 || key == nil || comparator == NULL)
        return [self binarySearch:key usingSelector:nil inRange:range];

//	check overflow?
    NSInteger min = range.location;
    NSInteger max = range.location + range.length - 1;

    while (min <= max)
    {
    	// http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
        const NSInteger mid = min + (max - min) / 2;
        switch (comparator(key, [self objectAtIndex:mid], context))
        {
            case NSOrderedSame:
                return mid;
            case NSOrderedDescending:
                min = mid + 1;
                break;
            case NSOrderedAscending:
                max = mid - 1;
                break;
        }
    }
    return -(min + 1);
}


#pragma mark Using NSSortDescriptors

-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors
{
    return [self binarySearch:key usingDescriptors:sortDescriptors inRange:NSMakeRange(0, self.count)];
}


/// internal helper
-(NSComparisonResult)_mroInternalCompare:(const NSArray const*)sortDescriptors a:(id)object1 b:(id)object2
{
    for (const NSSortDescriptor const *d in sortDescriptors)
    {
        const NSComparisonResult r = [d compareObject:object1 toObject:object2];
        if (r != NSOrderedSame)
            return r;
    }
    return NSOrderedSame;
}


-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors inRange:(NSRange)range
{
    NSLogD(@"[NSArray(MroBinarySearch) binarySearch:%@  usingDescriptors:]", key);
    if (self.count == 0 || key == nil || sortDescriptors == nil || sortDescriptors.count == 0)
        return [self binarySearch:key usingSelector:nil inRange:range];

//	check overflow?
    NSInteger min = range.location;
    NSInteger max = range.location + range.length - 1;

    while (min <= max)
    {
    	// http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
        const NSInteger mid = min + (max - min) / 2;
        switch ([self _mroInternalCompare:sortDescriptors a:key b:[self objectAtIndex:mid]])
        {
            case NSOrderedSame:
                return mid;
            case NSOrderedDescending:
                min = mid + 1;
                break;
            case NSOrderedAscending:
                max = mid - 1;
                break;
        }
    }
    return -(min + 1);
}

@end

Thanks for your code!

Can you let me know which license is used for distribution of this code?
I'd like to use this code for a commercial app so I need to check the license.

Happy coding! :)