Sha256: d988bfee68c91a157ba3fa67bd2a4f6b52acbf712f7a0468fd42f5c09ce87b2f
Contents?: true
Size: 1.5 KB
Versions: 268
Compression:
Stored size: 1.5 KB
Contents
#import "BinarySearchExample.h"
@implementation BinarySearch
- (instancetype)initWithArray:(NSArray<NSNumber *> *)array {
self = [super init];
if (self) {
// This binary search algorithm only works if the array is already is ascending order.
if ([array isEqualToArray:[array sortedArrayUsingSelector:@selector(compare:)]]) {
_list = array;
} else {
return nil;
}
}
return self;
}
- (NSInteger)searchFor:(int)number {
NSInteger middleIndex = [self middle];
int middle = [self.list[middleIndex] intValue];
if (middle == number) {
return middleIndex;
} else if (middle > number) {
NSArray *sublist = [self.list subarrayWithRange:NSMakeRange(0, middleIndex)];
BinarySearch *binary = [[BinarySearch alloc] initWithArray:sublist];
if (!binary) {
return NSNotFound;
}
return [binary searchFor:number];
} else { //!OCLint
NSUInteger length = self.list.count - middleIndex;
NSArray *sublist = [self.list subarrayWithRange:NSMakeRange(middleIndex, length)];
if ([sublist isEqualToArray:self.list]) {
return NSNotFound;
}
BinarySearch *binary = [[BinarySearch alloc] initWithArray:sublist];
if (!binary) {
return NSNotFound;
}
return [binary searchFor:number] + middleIndex;
}
}
- (NSInteger)middle {
return self.list.count / 2;
}
@end
Version data entries
268 entries across 268 versions & 1 rubygems