How to perform binary search on NSArray?

15

4

What is the simplest way to do a binary search on an (already) sorted NSArray?

Some potential ways I have spotted so far include:

  1. The use of CFArrayBSearchValues (mentioned here) - would this work on an NSArray?
  2. The method indexOfObject:inSortedRange:options:usingComparator: of NSArray assumes the array is sorted and takes an opts param of type NSBinarySearchingOptions - does this mean it performs a binary search? The docs just say:

    Returns the index, within a specified range, of an object compared with elements in the array using a given NSComparator block.

  3. Write my own binary search method (something along the lines of this).

I should add that I am programming for iOS 4.3+

Thanks in advance.

Barjavel

Posted 2012-06-25T23:33:48.107

Reputation: 928

Why not use NSDictionary instead? objectForKey: will search for you. – progrmr – 2012-06-25T23:56:52.687

Couple of questions on that - what's the benefit of a dictionary over array for an object search? Also, in order to use the method you have suggested wouldn't I need to know the key of the object? The reason I am searching the array for the object in the first place is that I do not know its index - if I changed to a dictionary implementation then this means I wouldn't know the key. – Barjavel – 2012-06-26T08:17:05.870

Answers

7

1 and 2 will both work. #2 is probably easier; it certainly doesn't make sense for that method to do anything other than a binary search (if the range is above a certain size, say). You could verify on a large array that it only does a small number of comparisons.

Jesse Rusak

Posted 2012-06-25T23:33:48.107

Reputation: 49 358

That's what I thought - the docs seem a little lacking in that they don't actually state it performs a binary search (they just heavily suggest). If I get around to doing the test you have suggested I'll be sure to post my results here. – Barjavel – 2012-06-26T08:22:14.450

15

The second option is definitely the simplest. Ole Begemann has a blog entry on how to use the NSArray's 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];
                              }];

See NSArray Binary Search

Max MacLeod

Posted 2012-06-25T23:33:48.107

Reputation: 21 430

1Keep in mind that you'll have to make sure the findIndex is below [sortedArray count] if you use the findIndex later on. This will crash if the item does not exist and you try to fetch it using sortedArray[findIndex]. – NatashaTheRobot – 2013-12-16T02:59:34.553

3

CFArrayBSearchValues should work—NSArray * is toll-free bridged with CFArrayRef.

Noah Witherspoon

Posted 2012-06-25T23:33:48.107

Reputation: 52 679

Thanks for the link. – Barjavel – 2012-06-26T08:20:48.117

3

I'm surprised that nobody mentioned the use of NSSet, which [when it contains objects with a decent hash, such as most Foundation data types] performs constant time lookups. Instead of adding your objects to an array, add then to a set instead (or add them to both if you need to retain a sorted order for other purposes [or alternatively on iOS 5.0 or Mac OS X 10.7 there is NSOrderedSet]).

To determine whether an object exists in a set:

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

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

Alternatively:

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

It is important to know that you will lose any performance benefit if you convert the array to a set each time you do a lookup, ideally you will be using a preconstructed set containing the objects you want to test.

dreamlax

Posted 2012-06-25T23:33:48.107

Reputation: 77 734

3

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

redEyeProgrammer

Posted 2012-06-25T23:33:48.107

Reputation: 56