How to perform binary search on NSArray?

Question

What is the simplest way to do a binary search on an (already) sorted NSArray?

Some potential ways I have spotted so far include:

1. The use of CFArrayBSearchValues (mentioned here) - would this work on an NSArray?

2. The method indexOfObject:inSortedRange:options:usingComparator: of NSArray assumes the array is sorted and takes an opts param of type NSBinarySearchingOptions - does this mean it performs a binary search? The docs just say:

   Returns the index, within a specified range, of an object compared with elements in the array using a given NSComparator block.

3. Write my own binary search method (something along the lines of this).

I should add that I am programming for iOS 4.3+

Thanks in advance.

Answer 1

The second option is definitely the simplest. Ole Begemann has a blog entry on how to use the NSArray's 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];
                              }];

See NSArray Binary Search

Answer 2

1 and 2 will both work. #2 is probably easier; it certainly doesn't make sense for that method to do anything other than a binary search (if the range is above a certain size, say). You could verify on a large array that it only does a small number of comparisons.