查找第一个值等于给定值得元素
有序数据集合中存在重复的数据，希望找到第一个值等于给定值的数据。比如下面这样一个有序数组，其中，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]之间。
网友评论