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

Question

对（已经）排序的进行二进制搜索的最简单方法是什么NSArray？

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

1. （这里CFArrayBSearchValues提到的）的使用——这对一个有用吗？NSArray

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

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

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 二分搜索

Answer 2

1 和 2 都可以。#2 可能更容易；除了二进制搜索之外，该方法当然没有任何意义（例如，如果范围大于某个大小）。您可以在大型数组上验证它只进行少量比较。

Answer 3

我很惊讶没有人提到使用NSSet，[当它包含具有良好哈希的对象时，例如大多数 Foundation 数据类型] 执行恒定时间查找。与其将对象添加到数组中，不如将其添加到集合中（如果您需要为其他目的保留排序顺序，则将它们添加到两者中[或者在 iOS 5.0 或 Mac OS X 10.7 上有NSOrderedSet]）。

要确定对象是否存在于集合中：

NSSet *mySet = [NSSet setWithArray:myArray]; // try to do this step only once

if ([mySet containsObject:someObject])
{
    // do something
}

或者：

NSSet *mySet = [NSSet setWithArray:myArray]; // try and do this step only once

id obj = [mySet member:someObject];

// obj is now set to nil if the object doesn't exist or it is
// set to an object that "isEqual:" to someObject (which could be
// someObject itself).

重要的是要知道，如果每次进行查找时都将数组转换为集合，那么您将失去任何性能优势，理想情况下，您将使用包含要测试的对象的预构建集合。

Answer 4

//Method to pass array and number we are searching for.
- (void)binarySearch:(NSArray *)array numberToEnter:(NSNumber *)key{


    NSUInteger  minIndex = 0;
    NSUInteger  maxIndex = array.count-1;
    NSUInteger  midIndex = array.count/2;


    NSNumber *minIndexValue = array[minIndex];
    NSNumber *midIndexValue = array[midIndex];
    NSNumber *maxIndexValue = array[maxIndex];

    //Check to make sure array is within bounds
    if (key > maxIndexValue || key < minIndexValue) {
        NSLog(@"Key is not within Range");
        return;
    }

    NSLog(@"Mid indexValue is %@", midIndexValue);

    //If key is less than the middleIndexValue then sliceUpArray and recursively call method again
    if (key < midIndexValue){
        NSArray *slicedArray = [array subarrayWithRange:NSMakeRange(minIndex, array.count/2)];
        NSLog(@"Sliced array is %@", slicedArray);
        [self binarySearch:slicedArray numberToEnter:key];

     //If key is greater than the middleIndexValue then sliceUpArray and recursively call method again
    } else if (key > midIndexValue) {
        NSArray *slicedArray = [array subarrayWithRange:NSMakeRange(midIndex+1, array.count/2)];
        NSLog(@"Sliced array is %@", slicedArray);
        [self binarySearch:slicedArray numberToEnter:key];

    } else {
      //Else number was found
        NSLog(@"Number found");
    }

}


//Call Method

@interface ViewController ()
@property(nonatomic)NSArray *searchArray;
@end


- (void)viewDidLoad {
    [super viewDidLoad];
//Initialize the array with 10 values
    self.searchArray = @[@1,@2,@3,@4,@5,@6,@7,@8,@9,@10];

//Call Method and search for any number
    [self binarySearch:self.searchArray numberToEnter:@5];
    // Do any additional setup after loading the view, typically from a nib.
}

Answer 5

CFArrayBSearchValues应该可以工作—— <code>NSArray *与CFArrayRef.