¿Cómo realizar búsquedas binarias en NSArray?

Question

¿Cuál es la forma más sencilla de realizar una búsqueda binaria en un archivo (ya) ordenado NSArray?

Algunas maneras posibles que ha detectado hasta la fecha incluyen:

1. El uso de CFArrayBSearchValues (mencionado here) - funcionaría esto en una NSArray?

2. El método de indexOfObject:inSortedRange:options:usingComparator:NSArray asume la matriz se clasifica y se toma un parámetro de tipo optsNSBinarySearchingOptions - ¿significa esto que realiza una búsqueda binaria? El docs acaba de decir:

   Devuelve el índice, dentro de un rango especificado, de un objeto en comparación con los elementos de la matriz utilizando un bloque de NSComparator dado.

3. Escriba mi propio método de búsqueda binario (algo similar a this).

debo añadir que estoy programando para iOS 4.3+

Gracias de antemano.

Answer 1

1 y 2 funcionarán ambos. # 2 es probablemente más fácil; ciertamente no tiene sentido que ese método haga otra cosa que no sea una búsqueda binaria (por ejemplo, si el rango está por encima de cierto tamaño). Puede verificar en una matriz grande que solo hace una pequeña cantidad de comparaciones.

Answer 2

CFArrayBSearchValues debería trabajar- NSArray * es toll-free bridged con CFArrayRef.

Answer 3

La segunda opción es definitivamente la más simple. Ole Begemann tiene una entrada de blog sobre cómo utilizar el NSArray 's indexOfObject:inSortedRange:options:usingComparator: método:

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

Ver NSArray Binary Search

Answer 4

Me sorprende que nadie ha mencionado el uso de NSSet, que [cuando contiene objetos con una hash decente, como la mayoría de los tipos de datos de Foundation] realiza búsquedas de tiempo constante. En lugar de agregar sus objetos a una matriz, agréguelos a un conjunto (o agréguelos a ambos si necesita conservar un orden ordenado para otros fines [o alternativamente en iOS 5.0 o Mac OS X 10.7 hay NSOrderedSet]).

para determinar si existe un objeto en un conjunto:

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

Es importante saber que va a perder ninguna ventaja de rendimiento si convierte la matriz de un conjunto cada vez que realiza una búsqueda, lo ideal es que utilice un conjunto preconstruido que contenga los objetos que desea probar.

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