gistfile1.mm

@interface NSArray (BinarySearch)
- (NSUInteger)indexOfObjectUsingBinarySearch:(id)obj;
@end

@implementation NSArray (BinarySearch)
// performs a binary search in the array, returning the index of the found object or NSNotFound
// this assumes the array is in sorted order according to the compare: selector
- (NSUInteger)indexOfObjectUsingBinarySearch:(id)obj {
    NSRange range = NSMakeRange(0, [self count]);
    while (range.length > 0) {
        NSUInteger pivotIdx = range.location + (range.length / 2); // center idx, rounded down
        id pivot = [self objectAtIndex:pivotIdx];
        switch ([obj compare:pivot]) {
            case NSOrderedSame:
                // we've found the object
                return pivotIdx;
            case NSOrderedAscending:
                // object is in the lower half
                range.length = pivotIdx - range.location;
                break;
            case NSOrderedDescending:
                // object is in the upper half
                range = NSMakeRange(pivotIdx+1, NSMaxRange(range) - (pivotIdx+1));
                break;
        }
    }
    return NSNotFound;
}
@end