二分查找变体上

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

有序数据集合中存在重复的数据，希望找到第一个值等于给定值的数据。比如下面这样一个有序数组，其中，a[5]、a[6]、a[7]的值都等于8，是重复的数据。希望查找第一个等于8的数据，也就是下标是5的元素。

代码实现如下：

@interface DMFirstEqualBinarySearch : NSObject

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

@end

@implementation DMFirstEqualBinarySearch

- (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) {
                low = mid + 1;
            } else if (tmpValue == targetValue) {
                if (mid == 0 || [[dataArray objectAtIndex:mid -1] integerValue] != targetValue) {
                    targetIndex = mid;
                    break;
                }
                high = mid - 1;
            }
        }
    }
    return targetIndex;
}

@end

@interface DMSearchDemo : NSObject

@end

@implementation DMSearchDemo

- (void)demo 
{   
    DMFirstEqualBinarySearch *firstEqualBinarySearch = [[DMFirstEqualBinarySearch alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:11]];
        [dataArray addObject:[NSNumber numberWithInteger:18]];
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        NSInteger targetIndex = [firstEqualBinarySearch binarySearch:[dataArray copy] targetValue:8];
        NSLog(@"变体二分查找算法查找8所在下标为%ld", (long)targetIndex);
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        targetIndex = [firstEqualBinarySearch binarySearch:[dataArray copy] targetValue:20];
        NSLog(@"变体二分查找算法查找20所在下标为%ld", (long)targetIndex);
    }
}

@end

a[mid]跟要查找的value的大小关系有三种情况：大于、小于、等于。对于a[mid] > value的情况，需要更新 high = mid - 1；对于 a[mid] < value 的情况，需要更新 low = mid + 1；那当a[mid] = value 的时候应该如何处理呢？
如果查找的是任意一个值等于给定值的元素，当a[mid]等于要查找的值时，a[mid]就是要找的元素。但是，如果求解的是第一个值等于给定值的元素，当a[mid]等于要查找的值时，就需要确认一下这个a[mid]是不是第一个值等于给定值的元素。
如果mid等于0，那这个元素已经是数组的第一个元素，那它肯定是要找的元素；如果mid不等于0，但a[mid]的前一个元素a[mid - 1]不等于value，那也说明a[mid]就是要找的第一个值等于给定值的元素。
如果经过检查之后发现a[mid]前面的一个元素a[mid - 1]也等于value，那说明此时的a[mid]肯定不是要查找的第一个值等于给定值的元素。那就更新high = mid - 1,因为要找的元素肯定出现在[low，mid - 1]之间。

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

代码实现如下：

@interface DMLastEqualBinarySearch : NSObject

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

@end

@implementation DMLastEqualBinarySearch

- (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) {
                low = 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 
{   
    DMLastEqualBinarySearch *lastEqualBinarySearch = [[DMLastEqualBinarySearch alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:11]];
        [dataArray addObject:[NSNumber numberWithInteger:18]];
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        NSInteger targetIndex = [lastEqualBinarySearch binarySearch:[dataArray copy] targetValue:8];
        NSLog(@"变体二分查找算法查找最后一个8所在下标为%ld", (long)targetIndex);
        
        NSLog(@"变体二分查找算法原始数据: %@", [dataArray componentsJoinedByString:@"  "]);
        targetIndex = [lastEqualBinarySearch binarySearch:[dataArray copy] targetValue:20];
        NSLog(@"变体二分查找算法查找最后一个20所在下标为%ld", (long)targetIndex);
    }
}

@end

当当a[mid] = value 的时候，如果a[mid]这个元素已经是数组中的最后一个元素了，那它肯定是要找的元素；如果a[mid]的后一个元素a[mid + 1]不等于value，那也说明a[mid]就是要找的最后一个值等于给定值的元素。
如果经过检查之后，发现a[mid]后面的一个元素a[mid + 1]也等于value，那说明当前的这个a[mid]并不是最后一个值等于给定值的元素。那就更新low = mid + 1,因为要找的元素肯定在a[mid+1, high]之间。