39 lines
1.1 KiB
Objective-C
39 lines
1.1 KiB
Objective-C
#import <Foundation/Foundation.h>
|
|
|
|
@interface NSArray (BinarySearchRecursive)
|
|
// Requires all elements of this array to implement a -compare: method which
|
|
// returns a NSComparisonResult for comparison.
|
|
// Returns NSNotFound when not found
|
|
- (NSInteger) binarySearch:(id)key inRange:(NSRange)range;
|
|
@end
|
|
|
|
@implementation NSArray (BinarySearchRecursive)
|
|
- (NSInteger) binarySearch:(id)key inRange:(NSRange)range {
|
|
if (range.length == 0)
|
|
return NSNotFound;
|
|
NSInteger mid = range.location + range.length / 2;
|
|
id midVal = self[mid];
|
|
switch ([midVal compare:key]) {
|
|
case NSOrderedAscending:
|
|
return [self binarySearch:key
|
|
inRange:NSMakeRange(mid + 1, NSMaxRange(range) - (mid + 1))];
|
|
case NSOrderedDescending:
|
|
return [self binarySearch:key
|
|
inRange:NSMakeRange(range.location, mid - range.location)];
|
|
default:
|
|
return mid;
|
|
}
|
|
}
|
|
@end
|
|
|
|
int main()
|
|
{
|
|
@autoreleasepool {
|
|
|
|
NSArray *a = @[@1, @3, @4, @5, @6, @7, @8, @9, @10];
|
|
NSLog(@"6 is at position %d", [a binarySearch:@6]); // prints 4
|
|
|
|
}
|
|
return 0;
|
|
}
|