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

• indexOfObject:inSortedRange:options:usingComparator:
• CFArrayBSearchValues

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

实例

#import "ViewController.h"

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    NSArray *sortedArray = @[@1,@2,@3,@4,@36,@35,@46,@49]; // must be sorted
    id searchObject = @4;
    NSRange searchRange = NSMakeRange(0, [sortedArray count]);
    NSUInteger findIndex = [sortedArray indexOfObject:searchObject
                                        inSortedRange:searchRange
                                              options:NSBinarySearchingFirstEqual
                                      usingComparator:^(id obj1, id obj2)
                            {
                                return [obj1 compare:obj2];
                            }];

    NSLog(@"findIndex is %d",findIndex);
}

- (void)didReceiveMemoryWarning {
    [super didReceiveMemoryWarning];
    // Dispose of any resources that can be recreated.
}

@end

输出

2016-03-17 15:45:00.417 SortedNSArrayDemo[58667:2052310] findIndex is 3

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);

Resource Reference

• http://www.isaced.com/post-241.html