objective-c - ordenamiento - busqueda binaria pseint

¿Cómo realizar una búsqueda binaria en NSArray?

Question

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

Algunas formas potenciales que he visto hasta ahora incluyen:

1. El uso de CFArrayBSearchValues (mencionado here ): ¿funcionaría en un NSArray ?

2. El método indexOfObject:inSortedRange:options:usingComparator: of NSArray asume que la matriz está ordenada y toma un NSBinarySearchingOptions opts de tipo NSBinarySearchingOptions . ¿Esto significa que realiza una búsqueda binaria? Los docs solo dicen:

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

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

Debo añadir que estoy programando para iOS 4.3+

Gracias por adelantado.

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 (si el rango está por encima de cierto tamaño, por ejemplo). Podría verificar en una matriz grande que solo hace un pequeño número de comparaciones.

Answer 2

La segunda opción es sin duda la más sencilla. Ole Begemann tiene una entrada de blog sobre cómo utilizar el indexOfObject:inSortedRange:options:usingComparator: NSArray indexOfObject:inSortedRange:options:usingComparator: method:

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 3

Me sorprende que nadie mencione el uso de NSSet , que [cuando contiene objetos con un 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, agregue luego a un conjunto en su lugar (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 un objeto existe en un conjunto:

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

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

Alternativamente:

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 perderá cualquier beneficio de rendimiento si convierte la matriz en un conjunto cada vez que realiza una búsqueda, idealmente, estará usando un conjunto preconstruido que contiene los objetos que desea probar.

Answer 4

CFArrayBSearchValues debería funcionar: NSArray * es un puente gratuito con CFArrayRef .

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