objective-c - 如何对 NSArray 进行二分查找？

Question

对(已)排序的 NSArray 进行二分查找的最简单方法是什么？

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

1. CFArrayBSearchValues 的使用(提到 here )- 这对 NSArray 有用吗？

2. NSArray 的方法 indexOfObject:inSortedRange:options:usingComparator: 假定数组已排序并采用 opts 参数输入 NSBinarySearchingOptions - 这是否意味着它执行二进制搜索？ docs就说:

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

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

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

提前致谢。

Answer 1

第二种选择绝对是最简单的。 Ole 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 Binary Search