Skip to content

Instantly share code, notes, and snippets.

@ole
Created April 20, 2010 12:41
Show Gist options
  • Save ole/372377 to your computer and use it in GitHub Desktop.
Save ole/372377 to your computer and use it in GitHub Desktop.
A binary search algorithm written in Objective-C/Cocoa for http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
//
// NSArray+BinarySearch.h
// BinarySearch
//
// Created by Ole Begemann on 19.04.10.
// Copyright 2010 Ole Begemann. All rights reserved.
//
#import <Foundation/Foundation.h>
@interface NSArray (BinarySearch)
- (NSInteger)binarySearch:(id)searchItem;
@end
//
// NSArray+BinarySearch.m
// BinarySearch
//
// Created by Ole Begemann on 19.04.10.
// Copyright 2010 Ole Begemann. All rights reserved.
//
#import "NSArray+BinarySearch.h"
@interface NSArray (BinarySearchPrivate)
- (NSInteger)binarySearch:(id)searchItem minIndex:(NSInteger)minIndex maxIndex:(NSInteger)maxIndex;
@end
@implementation NSArray (BinarySearch)
- (NSInteger)binarySearch:(id)searchItem
{
if (searchItem == nil)
return NSNotFound;
return [self binarySearch:searchItem minIndex:0 maxIndex:[self count] - 1];
}
- (NSInteger)binarySearch:(id)searchItem minIndex:(NSInteger)minIndex maxIndex:(NSInteger)maxIndex
{
// If the subarray is empty, return not found
if (maxIndex < minIndex)
return NSNotFound;
NSInteger midIndex = (minIndex + maxIndex) / 2;
id itemAtMidIndex = [self objectAtIndex:midIndex];
NSComparisonResult comparison = [searchItem compare:itemAtMidIndex];
if (comparison == NSOrderedSame)
return midIndex;
else if (comparison == NSOrderedAscending)
return [self binarySearch:searchItem minIndex:minIndex maxIndex:midIndex - 1];
else
return [self binarySearch:searchItem minIndex:midIndex + 1 maxIndex:maxIndex];
}
@end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment