Though CFArray comes with binary search capability, NSArray does not – at least not within the iPhone SDK. The indexOfObject:inSortedRange:options:usingComparator: can’t be found.
Plus the CFArrayBSearchValues doesn’t tell you whether the key actually is part of the list or not. That’s what the Java JDK does, so let’s implement some category methods
-(NSInteger)binarySearch:(id)key; -(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator; -(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator inRange:(NSRange)range; -(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context; -(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range; -(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors; -(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors inRange:(NSRange)range;
ourselves, like
-(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); }
See the full interface + implementation + testcase without html encoding dirt at github.