Jak przeprowadzić wyszukiwanie binarne w NSArray?

Question

Jaki jest najprostszy sposób wyszukiwania binarnego na (już) posortowanym NSArray?

niektórych potencjalnych sposobów I zauważyli dotychczas to:

1. Zastosowanie CFArrayBSearchValues (wspomniane here) - to będzie działać na NSArray?

2. Sposób indexOfObject:inSortedRange:options:usingComparator: z NSArray zakłada tablica jest posortowana i bierze opts param typu NSBinarySearchingOptions - to znaczy, że wykonuje wyszukiwanie binarne? docs to znaczy:

   Zwraca wskaźnika w określonym zakresie, o przedmiotu w porównaniu z elementami w macierzy z wykorzystaniem danego bloku NSComparator.

3. Napisz moją własną metodę wyszukiwania binarnego (coś podobnego do linii this).

Dodam, że jestem programowania dla iOS 4.3+

Dzięki z góry.

Answer 1

1 i 2 będą działać. # 2 jest prawdopodobnie łatwiejsze; Z pewnością nie ma sensu, aby ta metoda robiła coś innego niż wyszukiwanie binarne (jeśli zakres jest powyżej pewnego rozmiaru, powiedzmy). Na dużej tablicy można zweryfikować, że wykonuje tylko niewielką liczbę porównań.

Answer 2

CFArrayBSearchValues powinien działać - NSArray * jest toll-free bridged z CFArrayRef.

Answer 3

Druga opcja jest zdecydowanie najprostsza. Ole Begemann posiada wpis w blogu, w jaki sposób korzystać z NSArray „s indexOfObject:inSortedRange:options:usingComparator: metody:

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]; 
           }]; 

Zobacz NSArray Binary Search

Answer 4

Dziwię się, że nikt nie wspomniał o wykorzystanie NSSet, która [gdy zawiera obiekty z przyzwoite hash, takie jak większość typów danych Foundation] wykonuje stałe wyszukiwanie czasu. Zamiast dodawać obiekty do tablicy, należy zamiast tego dodać do zestawu (lub dodać je do obu, jeśli zachowasz posortowaną kolejność do innych celów [lub alternatywnie na iOS 5.0 lub Mac OS X 10.7 jest NSOrderedSet]).

Aby ustalić, czy dany obiekt istnieje w zestawie:

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

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

Alternatywnie:

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

Ważne jest, aby wiedzieć, że stracisz żadnych korzyści wydajności konwertowania tablicę do zestawu za każdym razem, gdy wykonujesz wyszukiwanie, najlepiej będziesz używał wstępnie skonstruowanego zestawu zawierającego obiekty, które chcesz przetestować.

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