如何在NSArray上执行二进制search？
在（已经）sorting的NSArray上进行二分search最简单的方法是什么？
到目前为止，我发现的一些潜在的方式包括：
- 使用
CFArrayBSearchValues（ 这里提到） – 这将工作在NSArray？ -
NSArrayindexOfObject:inSortedRange:options:usingComparator:方法假定数组被sorting，并且需要NSBinarySearchingOptionstypes的opts参数 – 这是否意味着它执行二分search？ 文档只是说：使用给定的NSComparator块，将指定范围内的对象的索引与数组中的元素进行比较。
-
写我自己的二进制search方法（沿线的东西）。
我应该补充说，我正在为iOS 4.3+编程
提前致谢。
1和2都将工作。 ＃2可能更容易; 对于这种方法来说，除了二分search之外，如果范围超过一定的大小，这当然是没有意义的。 你可以在一个大的数组上进行validation，它只进行less量的比较。
第二个选项绝对是最简单的。 Ole Begemann有关于如何使用NSArray的indexOfObject:inSortedRange:options:usingComparator:的博客条目indexOfObject:inSortedRange:options:usingComparator: method：
NSArray *sortedArray = ... // must be sorted id searchObject = ... NSRange searchRange = NSMakeRange(0, [sortedArray count]); NSUInteger findIndex = [sortedArray indexOfObject:searchObject inSortedRange:searchRange options:NSBinarySearchingFirstEqual usingComparator:^(id obj1, id obj2) { return [obj1 compare:obj2]; }];
请参阅NSArray二进制search
CFArrayBSearchValues应该工作 – NSArray * 免费与CFArrayRef 桥接 。
令我惊讶的是，没有人提到使用NSSet ，当它包含具有像样的散列的对象，比如大多数基础数据types时，执行恒定时间查找。 而不是将你的对象添加到一个数组，而是添加到一个集合，或者如果你需要保留一个sorting顺序用于其他目的[或者在iOS 5.0或Mac OS X 10.7有NSOrderedSet ]）添加到两者。
要确定一个对象是否存在于一个集合中：
NSSet *mySet = [NSSet setWithArray:myArray]; // try to do this step only once if ([mySet containsObject:someObject]) { // do something }
或者：
NSSet *mySet = [NSSet setWithArray:myArray]; // try and do this step only once id obj = [mySet member:someObject]; // obj is now set to nil if the object doesn't exist or it is // set to an object that "isEqual:" to someObject (which could be // someObject itself).
重要的是要知道，如果每次查找时将数组转换为一个集合，就会失去性能优势，理想情况下，您将使用包含要testing的对象的预构build集合。
//Method to pass array and number we are searching for. - (void)binarySearch:(NSArray *)array numberToEnter:(NSNumber *)key{ NSUInteger minIndex = 0; NSUInteger maxIndex = array.count-1; NSUInteger midIndex = array.count/2; NSNumber *minIndexValue = array[minIndex]; NSNumber *midIndexValue = array[midIndex]; NSNumber *maxIndexValue = array[maxIndex]; //Check to make sure array is within bounds if (key > maxIndexValue || key < minIndexValue) { NSLog(@"Key is not within Range"); return; } NSLog(@"Mid indexValue is %@", midIndexValue); //If key is less than the middleIndexValue then sliceUpArray and recursively call method again if (key < midIndexValue){ NSArray *slicedArray = [array subarrayWithRange:NSMakeRange(minIndex, array.count/2)]; NSLog(@"Sliced array is %@", slicedArray); [self binarySearch:slicedArray numberToEnter:key]; //If key is greater than the middleIndexValue then sliceUpArray and recursively call method again } else if (key > midIndexValue) { NSArray *slicedArray = [array subarrayWithRange:NSMakeRange(midIndex+1, array.count/2)]; NSLog(@"Sliced array is %@", slicedArray); [self binarySearch:slicedArray numberToEnter:key]; } else { //Else number was found NSLog(@"Number found"); } } //Call Method @interface ViewController () @property(nonatomic)NSArray *searchArray; @end - (void)viewDidLoad { [super viewDidLoad]; //Initialize the array with 10 values self.searchArray = @[@1,@2,@3,@4,@5,@6,@7,@8,@9,@10]; //Call Method and search for any number [self binarySearch:self.searchArray numberToEnter:@5]; // Do any additional setup after loading the view, typically from a nib. }