Skip to content

Instantly share code, notes, and snippets.

@antonio081014
Last active December 3, 2015 00:19
Show Gist options
  • Save antonio081014/33f7ca2d616b2a4e4925 to your computer and use it in GitHub Desktop.
Save antonio081014/33f7ca2d616b2a4e4925 to your computer and use it in GitHub Desktop.
This is the Binary Search implementation written in Objective-C.
/**
* Standard Binary Search.
*/
- (BOOL)binarySearch:(NSInteger)number inArray:(NSArray *)array;
/**
* Find the very first element index in an ordered array that satisfy with crateria, then return the index.
* Otherwise, return -1.
* This algorithm implemented with binary search.
*/
- (NSInteger)leastXFromIndex:(NSInteger)low
toIndex:(NSInteger)high
withTrueCriterial:(BOOL(^)(NSInteger index))crateria;
/**
* Find the very last element index in an ordered array that does not satisfy with crateria, then return the index.
* Otherwise, return -1.
* This algorithm implemented with binary search.
*/
- (NSInteger)greatestXFromIndex:(NSInteger)low
toIndex:(NSInteger)high
withFalseCriterial:(BOOL(^)(NSInteger index))crateria;
- (BOOL)binarySearch:(NSInteger)number inArray:(NSArray *)array
{
NSInteger left = 0;
NSInteger right = array.count - 1;
while(left <= right) {
NSInteger mid = (left + right) / 2;
if([array[mid] integerValue] < number) {
left = mid + 1;
} else if([array[mid] integerValue] > number) {
right = mid - 1;
} else {
return YES;
}
}
return NO;
}
- (NSInteger)leastXFromIndex:(NSInteger)low
toIndex:(NSInteger)high
withTrueCriterial:(BOOL(^)(NSInteger index))crateria
{
while(low < high) {
NSInteger mid = (low + high) / 2;
if (crateria(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
if(!crateria(low)) {
// Nothing works with this crateria.
return -1;
}
return low;
}
- (NSInteger)greatestXFromIndex:(NSInteger)low
toIndex:(NSInteger)high
withFalseCriterial:(BOOL(^)(NSInteger index))crateria
{
while(low < high) {
NSInteger mid = (low + high) / 2;
if(crateria(mid)) {
high = mid - 1;
} else {
low = mid;
}
}
if(crateria(low)) {
// Crateria is true for every element in the array.
return -1;
}
return low;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment