Làm thế nào để thực hiện tìm kiếm nhị phân trên NSArray?

Question

Cách đơn giản nhất để thực hiện tìm kiếm nhị phân trên một (đã) được sắp xếp NSArray là gì?

Một số cách tiềm năng tôi đã phát hiện cho đến nay bao gồm:

1. Việc sử dụng CFArrayBSearchValues (nêu here) - sẽ làm việc này trên một NSArray?

2. Phương pháp indexOfObject:inSortedRange:options:usingComparator: của NSArray giả định mảng được sắp xếp và có một tham số opts của loại NSBinarySearchingOptions - điều này có nghĩa là nó thực hiện tìm kiếm nhị phân? Số docs chỉ cần nói:

   Trả về chỉ mục, trong phạm vi được chỉ định của đối tượng so với các phần tử trong mảng sử dụng khối NSComparator đã cho.

3. Viết phương thức tìm kiếm nhị phân của riêng tôi (thứ gì đó dọc theo dòng this).

tôi nên thêm rằng tôi đang lập trình cho iOS 4.3+

Cảm ơn trước.

Answer 1

1 và 2 sẽ hoạt động. # 2 có lẽ dễ dàng hơn; nó chắc chắn không có ý nghĩa cho phương pháp đó để làm bất cứ điều gì khác hơn là một tìm kiếm nhị phân (nếu phạm vi là trên một kích thước nhất định, nói). Bạn có thể xác minh trên một mảng lớn mà nó chỉ làm một số lượng nhỏ so sánh.

Answer 2

CFArrayBSearchValues sẽ hoạt động— NSArray * là toll-free bridged với CFArrayRef.

Answer 3

Tùy chọn thứ hai chắc chắn là đơn giản nhất. Ole Begemann có một blog entry về cách sử dụng phương pháp này indexOfObject:inSortedRange:options:usingComparator: 's 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]; 
           }]; 

Xem NSArray Binary Search

Answer 4

Tôi ngạc nhiên mà không ai nhắc đến việc sử dụng các NSSet, đó [khi nó chứa các đối tượng với một băm phong nha, chẳng hạn như hầu hết các loại dữ liệu Foundation] thực hiện tra cứu thời gian không đổi. Thay vì thêm đối tượng của bạn vào mảng, hãy thêm vào một tập hợp thay thế (hoặc thêm chúng vào cả hai nếu bạn cần giữ lại thứ tự sắp xếp cho các mục đích khác [hoặc cách khác trên iOS 5.0 hoặc Mac OS X 10.7 có NSOrderedSet]).

Để xác định xem một đối tượng tồn tại trong một bộ:

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

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

Hoặc:

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

Điều quan trọng là phải biết rằng bạn sẽ mất bất kỳ lợi ích hiệu suất nếu bạn chuyển đổi mảng đến một tập mỗi khi bạn thực hiện tra cứu, lý tưởng là bạn sẽ sử dụng một bộ cấu hình sẵn có chứa các đối tượng bạn muốn kiểm tra.

Answer 5

//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. 
}