Performing Binary Searches with NSArray


I had an application which I'm going to be vague about. It needed to very frequently see if an item was in an NSArray that contained a very large number of items. Performance tools shows that my code was spending a lot of time doing these lookups. I decided to see if I could do a binary seacrh in this array instead of a linear search. My application run time went from a couple hours to about 13 minutes. That made me feel like a real programming stud.

What We Need

I'm not going to explain binary searches to you. But to perform a binary search, the items you want to seach need to be sorted. So, you can sort the entire list every time before you do a search, or you can keep the list in sorted order. My plan keeps the list in sorted order. So, what we need is a method that inserts an item to the array keeping it in sorted order, and a method that performs the search on the sorted items.

The Prototypes

Here are the declarations of the methods I added:
@interface NSMutableArray (JAVBinarySearchAdditions)
- (void) addObject:(id)object intoArraySortedBy:(SEL)compareSelector;
- (unsigned) indexOfObject:(id)object inArraySortedBy:(SEL)compareSelector;
So what you'll need is a compare: method. Lots of Foundations classes like NSString already have a compare: method. If you're storing your own custom objects in the array, you'll need to write a compare: method for your object.

Using It

So this is how you would use this new binary searching array. To add items:
NSMutableArray* justSomeArray = [NSMutableArray new];
WayCoolObject* obj = [WayCoolObject new];
[justSomeArray addObject:obj intoArraySortedBy:@selector(compare:)];
And then to retrieve items:
unsigned indexOfObject = [justSomeArray indexOfObject:obj inArraySortedBy:@selector(compare:)];
if (indexOfObject == NSNotFound)
	NSLog(@"Item not found");
So there you have it.

The Code

I wrote the code with lots of comments. So you can follow along if you want. I'm not going to explain it again here.

Download the code

I did all the work, and now you can download free code. Lucky you. Consider sending me money.

Download (2K)

Extreme Mac OS X Programming. Copyright 2005 John A. Vink