二分查找变体下

查找第一个大于等于给定值的元素

在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于5的元素，那就是6。
代码实现如下:

@interface DMFirstGreaterThanOrEqualBinarySearch : NSObject

/*
 *  二分查找变体算法，第一个值大于等于给定值的元素
 *  返回：-1时表示没找到, 找到时返回下标
 */
- (NSInteger)binarySearch:(NSArray *)dataArray targetValue:(NSInteger)targetValue;

@end

@implementation DMFirstGreaterThanOrEqualBinarySearch

- (NSInteger)binarySearch:(NSArray *)dataArray targetValue:(NSInteger)targetValue
{
    NSInteger targetIndex = -1;
    if ([dataArray count] > 0) {
        NSInteger low = 0;
        NSInteger high = [dataArray count] - 1;
        NSInteger mid = low + (high - low) / 2;
        while (low <= high) {
            mid = low + (high - low) / 2;
            NSNumber *tmpNum = [dataArray objectAtIndex:mid];
            NSInteger tmpValue = [tmpNum integerValue];
            if (tmpValue >= targetValue) {
                if (mid == 0 || [[dataArray objectAtIndex:mid - 1] integerValue] < targetValue) {
                    targetIndex = mid;
                    break;
                }
                high = mid - 1;
            } else if (tmpValue < targetValue) {
                low = mid + 1;
            }
        }
    }
    return targetIndex;
}

@end

@interface DMSearchDemo : NSObject

@end

@implementation DMSearchDemo

- (void)demo 
{   
    DMFirstGreaterThanOrEqualBinarySearch *firstGreaterThanOrEqualBinarySearch = [[DMFirstGreaterThanOrEqualBinarySearch alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:7]];
        [dataArray addObject:[NSNumber numberWithInteger:10]];
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        NSInteger targetIndex = [firstGreaterThanOrEqualBinarySearch binarySearch:[dataArray copy] targetValue:5];
        NSLog(@"变体二分查找算法查找第一个大于等于5所在下标为%ld", (long)targetIndex);
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        targetIndex = [firstGreaterThanOrEqualBinarySearch binarySearch:[dataArray copy] targetValue:20];
        NSLog(@"变体二分查找算法查找大于等于20所在下标为%ld", (long)targetIndex);
    }
}

@end

如果a[mid]小于要查找的值value,那要找的值肯定a[mid+1,high]之间，所以，更新low = mid + 1。
对于a[mid]大于等于给定值value的情况，要先看一下这个a[mid]是不是要找的第一个值大于等于给定值的元素。如果a[mid]前面已经没有元素，或者前面一个元素小于要查找的值value，那a[mid]就是要找的元素。如果a[mid-1]也大于等于要查找的值value，那说明要查找的元素在a[low,mid-1]之间，所以，更新hig = mid - 1。

查找最后一个小于等于给定值的元素

在有序数组中，查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于7 的元素就是6。
代码实现如下：

@interface DMLastLessThanOrEqualBinarySearch : NSObject

/*
 *  二分查找变体算法，最后一个值小于等于给定值的元素
 *  返回：-1时表示没找到, 找到时返回下标
 */
- (NSInteger)binarySearch:(NSArray *)dataArray targetValue:(NSInteger)targetValue;

@end

@implementation DMLastLessThanOrEqualBinarySearch

- (NSInteger)binarySearch:(NSArray *)dataArray targetValue:(NSInteger)targetValue
{
    NSInteger targetIndex = -1;
    if ([dataArray count] > 0) {
        NSInteger low = 0;
        NSInteger high = [dataArray count] - 1;
        NSInteger mid = low + (high - low) / 2;
        while (low <= high) {
            mid = low + (high - low) / 2;
            NSNumber *tmpNum = [dataArray objectAtIndex:mid];
            NSInteger tmpValue = [tmpNum integerValue];
            if (tmpValue > targetValue) {
                high = mid - 1;
            } else if (tmpValue <= targetValue) {
                if (mid == [dataArray count] - 1 || [[dataArray objectAtIndex:mid + 1] integerValue] > targetValue) {
                    targetIndex = mid;
                    break;
                }
                low = mid + 1;
            }
        }
    }
    return targetIndex;
}

@end

@interface DMSearchDemo : NSObject

@end

@implementation DMSearchDemo

- (void)demo 
{   
    DMLastLessThanOrEqualBinarySearch *lessThanOrEqualBinarySearch = [[DMLastLessThanOrEqualBinarySearch alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:9]];
        [dataArray addObject:[NSNumber numberWithInteger:10]];
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        NSInteger targetIndex = [lessThanOrEqualBinarySearch binarySearch:[dataArray copy] targetValue:7];
        NSLog(@"变体二分查找算法查找最后一个小于等于7所在下标为%ld", (long)targetIndex);
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        targetIndex = [lessThanOrEqualBinarySearch binarySearch:[dataArray copy] targetValue:2];
        NSLog(@"变体二分查找算法查找最后一个小于等于2所在下标为%ld", (long)targetIndex);
    }
}

@end

如果a[mid]大于要查找的值value，那要查找的值肯定在a[low, mid - 1]之间，所以，更新high = mid - 1。
如果a[mid]小于等于要查找的值value，要先看下a[mid]是不是要找的最后一个值小于等于给定值的元素。如果a[mid]后面已经没有元素了，或者后面一个元素大于要查找的值value，那a[mid]就是要找的元素。如果a[mid + 1]也小于等于要找的值value，那说明要查找的元素在a[mid + 1, high]之间，所以，更新low = mid + 1。