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