[Objective-C] NSArray的二分查找

二分查找(也叫折半查找),是至今应用比较多的一种搜索算法。速度快,比较次数少,在Objective-C中的NSArray至少有三种方法可以进行二分查找:

NSArray的二分查找方法

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];
                                  }];

###CFArray的二分查找方法

    NSMutableArray *sortedArray = [NSMutableArray arrayWithObjects: @"Alice", @"Beth", @"Carol",@"Ellen",nil];
    
    //Where is "Beth"?
    unsigned index = (unsigned)CFArrayBSearchValues((CFArrayRef)sortedArray,
                                                    CFRangeMake(0, CFArrayGetCount((CFArrayRef)sortedArray)),
                                                    (CFStringRef)@"Beth",
                                                    (CFComparatorFunction)CFStringCompare,
                                                    NULL);
    
    if (index < [sortedArray count] && [@"Beth" isEqualToString:sortedArray[index]])
                                        {
                                            NSLog(@"Beth was found at index %u", index);
                                        } else {
                                            NSLog(@"Beth was not found (index is beyond the bounds of sortedArray)");
                                        }
                                        
                                        //Where should we insert "Debra"?
                                        unsigned insertIndex = (unsigned)CFArrayBSearchValues((CFArrayRef)sortedArray,
                                                                                              CFRangeMake(0, CFArrayGetCount((CFArrayRef)sortedArray)),
                                                                                              (CFStringRef)@"Debra",
                                                                                              (CFComparatorFunction)CFStringCompare,
                                                                                              NULL);
                                        [sortedArray insertObject:@"Debra" atIndex:insertIndex];
                                        NSLog(@"%@",sortedArray);

自己编写二分查找算法

int main(int argc, const char * argv[])
{
    @autoreleasepool {

        // Conceptual tutorial
        NSArray *numberArray = @[@1, @3, @27, @36, @42, @70, @82];
        
        NSNumber *searchNum = @70;
        
        NSUInteger mid;
        NSUInteger min = 0;
        NSUInteger max = [numberArray count] - 1;
        
        BOOL found = NO;
        
        while (min <= max) {
            
            mid = (min + max)/2;
            
            if ([searchNum intValue] == [numberArray[mid] intValue]) {
                NSLog(@"We found the number! It is at index %lu", mid);
                found = YES;
                break;
            } else if ([searchNum intValue] < [numberArray[mid] intValue]) {
                max = mid - 1;
            } else if ([searchNum intValue] > [numberArray[mid] intValue]) {
                min = mid + 1;
            }
        }
        if (!found) {
            NSLog(@"The number was not found.");
        }
    }
    return 0;
}

参考资料: