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
1-(NSInteger)binarySearch:(id)key;
2-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator;
3-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator inRange:(NSRange)range;
4-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context;
5-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range;
6-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors;
7-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors inRange:(NSRange)range;ourselves, like
1-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range
2{
3 NSLogD(@"[NSArray(MroBinarySearch) binarySearch:%@ usingFunction:]", key);
4 if(self.count == 0 || key == nil || comparator == NULL)
5 return [self binarySearch:key usingSelector:nil inRange:range];
6
7// check overflow?
8 NSInteger min = range.location;
9 NSInteger max = range.location + range.length - 1;
10
11 while (min < = max)
12 {
13 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
14 const NSInteger mid = min + (max - min) / 2;
15 switch (comparator(key, [self objectAtIndex:mid], context))
16 {
17 case NSOrderedSame:
18 return mid;
19 case NSOrderedDescending:
20 min = mid + 1;
21 break;
22 case NSOrderedAscending:
23 max = mid - 1;
24 break;
25 }
26 }
27 return -(min + 1);
28}See the full interface + implementation + testcase without html encoding dirt at github.
