Kata2 Binary Search

I did my second Kata this morning. I thought I'd tackle the binary search problem in following with http://codekata.pragprog.com

The idea here is that you have some huge, but sorted, list and you need to find a single element within that list as efficiently as possible. As lists grow in size just traversing through the list element by element can take a really long time for higher numbers.

The binary search solution basically means you start in the middle continually divide the list in half until you find your element. For huge lists it's excellent because it doesn't matter where the desired element is in the list, it will always find it quickly, one drawback though it will more often than not, take several searches to locate the element. So you need to weigh the efficiency lost against the efficiency gained. 

I'm quite proud of my attempt. I've tested it with a list of 50,000,000 integers and it never takes more than 26 searches to find any element. It'll support an array of any size and it should support any data type, but I'll need to test that at a later time. This is a recursive approach as it was the approach that comes most naturally to me. I'm going to have a look at an iterative at a later time.

This was developed using TDD, kind of. I had to test this from a few different directions at once, namely efficiency and accuracy. I couldn't work out a good way of testing for them both at the same time so I'm leaving what test code I did end up with out of this post.

 -(NSNumber*)binarySearch:(NSArray*)array forInt:(NSNumber*)anInt {  
   int numberOfSearches = 1;  
   int min = 0;  
   int max = array.count;  
   int searchingFor = [anInt integerValue];  
   int indexOfGuess = [array indexOfObject:[array objectAtIndex:(max + min) / 2]];  
   int guess = [[array objectAtIndex:indexOfGuess] integerValue];  
   NSLog(@"%d searches", numberOfSearches);  
   while (searchingFor != guess){  
     if (max - min <= 2){  
       return [NSNumber numberWithInt:-1];  
     }  
     if (searchingFor < guess){  
       max = indexOfGuess;  
     }  
     if (searchingFor > guess){  
       min = indexOfGuess;  
     }  
     guess = [[array objectAtIndex:(max + min) / 2] integerValue];  
     indexOfGuess = [array indexOfObject:[array objectAtIndex:(max + min) / 2]];  
     numberOfSearches++;  
     NSLog(@"%d searches", numberOfSearches);  
   }  
   return [NSNumber numberWithInt:indexOfGuess];  
 }