Come eseguire la ricerca binaria su NSArray?

Question

Qual è il modo più semplice per eseguire una ricerca binaria su un (già) ordinato NSArray?

Alcuni potenziali modi che hai trovato finora includono:

1. L'uso di CFArrayBSearchValues (menzionato here) - sarebbe questo lavoro su un NSArray?

2. Il metodo indexOfObject:inSortedRange:options:usingComparator: di NSArray presuppone che l'array sia ordinato e prende un parametro opts di tipo NSBinarySearchingOptions - significa che esegue una ricerca binaria? Il docs solo dire:

   restituisce l'indice, in un intervallo specificato, di un oggetto rispetto elementi dell'array utilizzando un determinato blocco NSComparator.

3. Scrivere il mio metodo di ricerca binario (qualcosa sulla falsariga di this).

Vorrei aggiungere che io sono di programmazione per iOS 4.3 e versioni successive

Grazie in anticipo.

Answer 1

1 e 2 funzioneranno entrambi. # 2 è probabilmente più facile; certamente non ha senso che quel metodo faccia qualcosa di diverso da una ricerca binaria (se l'intervallo è superiore ad una certa dimensione, diciamo). È possibile verificare su un array di grandi dimensioni solo un numero limitato di confronti.

Answer 2

CFArrayBSearchValues dovrebbe funzionare- NSArray * è toll-free bridged con CFArrayRef.

Answer 3

La seconda opzione è sicuramente la più semplice. Ole Begemann ha un blog su come utilizzare il metodo indexOfObject:inSortedRange:options:usingComparator: s' il 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]; 
           }]; 

Vedi NSArray Binary Search

Answer 4

Sono sorpreso che nessuno ha menzionato l'uso di NSSet, che [quando contiene oggetti con una hash decente, come la maggior parte dei tipi di dati Foundation] esegue ricerche a tempo costante. Invece di aggiungere gli oggetti a un array, aggiungi invece a un set (o aggiungili ad entrambi se hai bisogno di mantenere un ordine ordinato per altri scopi [o in alternativa su iOS 5.0 o Mac OS X 10.7 c'è NSOrderedSet]).

per determinare se esiste un oggetto in un set:

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

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

alternativa:

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

E 'importante sapere che si perde alcun beneficio delle prestazioni se si converte l'array a un set ogni volta che eseguirai una ricerca, idealmente utilizzerai un set precostruito contenente gli oggetti che vuoi testare.

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