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