如何在NSArray上执行二进制搜索？

Question

在(已经)排序上进行二进制搜索的最简单方法是什么NSArray？

到目前为止我发现的一些潜在方法包括:

1. 使用CFArrayBSearchValues(这里提到) - 这会起作用NSArray吗？

2. 该方法indexOfObject:inSortedRange:options:usingComparator:的NSArray假定数组进行排序,并采取一种opts类型的PARAM NSBinarySearchingOptions-这意味着它执行二进制搜索？该文档只是说:

   返回对象的指定范围内的索引与使用给定NSComparator块的数组中的元素进行比较.

3. 编写我自己的二进制搜索方法(类似于此).

我应该补充一点,我正在为iOS 4.3+编程

提前致谢.

Answer 1

第二种选择绝对是最简单的.奥莱Begemann对如何使用博客条目NSArray的indexOfObject:inSortedRange:options:usingComparator:方法:

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二进制搜索

Answer 2

1和2都有效.#2可能更容易; 除了二进制搜索之外,对于该方法做任何事情当然没有意义(如果范围高于某个大小,比方说).您可以在大型阵列上验证它只进行少量比较.