我正在尝试使用indexOfObject:inSortedRange:options:usingComparator:在数组上实现简单的二叉搜索，但这种方法的行为并不完全符合我的预期，我不知道错过了什么。
让我们深入了解细节：
- 我尝试查找项目的数组是一个名为
Citywith 的自定义对象，上面有一个NSString类型的readableName属性。可读名称的示例值类似于Alabama, US。 - 数组已根据
readableName属性按字母顺序排序。 - 我试图使用这种二叉搜索实现的是能够根据搜索的前缀过滤数组，例如，如果搜索
Ams，我可以过滤以"Ams"开头的城市，如阿姆斯特丹、阿姆斯特尔芬等。 - 由于数组已排序，我正在尝试找到具有此前缀的第一个项目和具有此前缀的最后一个项目，并从两者之间的项目创建一个子数组。
- 以下是我用来搜索包含具有给定前缀的城市的范围的头部和尾部的方法：
+ (FilterRange *)findRangeHeadAndTailForPrefix:(NSString *)prefix inCityArray:(NSArray *)array {
FilterRange *result = [[FilterRange alloc] init];
result.startIndex = [self findRangeBordersForPrefix:prefix inArray:array lookingForHead:YES];
result.endIndex = [self findRangeBordersForPrefix:prefix inArray:array lookingForHead:NO];
return result;
}
+ (long)findRangeBordersForPrefix:(NSString *)prefix inArray:(NSArray *)array lookingForHead:(BOOL)shouldLookForHead {
NSRange searchRange = NSMakeRange(0, [array count]);
long foundIndex = [array indexOfObject:prefix
inSortedRange:searchRange
options:(shouldLookForHead ? NSBinarySearchingFirstEqual : NSBinarySearchingLastEqual)
usingComparator:^(id obj1, id obj2)
{
City *castedCity = (City *)([obj1 isKindOfClass:[City class]] ? obj1 : obj2);
NSString *castedPrefix = (NSString *)([obj1 isKindOfClass:[City class]] ? obj2 : obj1);
NSComparisonResult comparisonResult = ([[[castedCity readableName] lowercaseString] hasPrefix:[castedPrefix lowercaseString]] ? NSOrderedSame :
[[[castedCity readableName] lowercaseString] compare:[castedPrefix lowercaseString]]);
return comparisonResult;
}];
return foundIndex;
}
问题在于indexOfObject:inSortedRange:options:usingComparator:方法的行为，下面是它的行为方式(使用断点和比较器的逐步执行看到了这一点(：
- 对于 startIndex，使用数组中的最后一个对象和前缀调用比较器，结果
NSOrderedDescending - 然后使用数组中的第一个对象和前缀调用比较器，结果
NSOrderedAscending - 然后，它立即停止搜索和比较其他数组项，并返回最大值
long数值。 - 结束索引也会发生同样的情况
因此，搜索从未正确执行。 请注意，我不想使用filterUsingPredicate，因为它的时间很复杂。数组已经排序，因此可以通过二进制搜索实现更好的效率水平。
有没有人知道我可能错过了什么。我想有一些非常明显的东西，我没有注意它。 任何帮助或想法都非常感谢:)
规范化
我看到的第一个问题是你正在使用lowercase字符串，这对重音字符效果不佳，......首先，让我们编写一些帮助程序来规范化字符串。
@interface NSString(Normalize)
- (NSString *)normalized;
@end
@implementation NSString(Normalize)
- (NSString *)normalized {
NSMutableString *result = [NSMutableString stringWithString:self];
CFStringTransform((__bridge CFMutableStringRef)result, NULL, kCFStringTransformStripCombiningMarks, NO);
return [result lowercaseString];
}
@end
此方法返回带有剥离组合标记的小写字符串。不是一个非常高性能的版本，但您知道这里需要做什么。
缓存
规范化可能很昂贵，让我们缓存它。
@interface City: NSObject
@property(nonatomic, strong) NSString *readableName;
@property(nonatomic, strong, readonly) NSString *normalizedReadableName;
@end
@implementation City {
NSString *_normalizedReadableName;
}
- (instancetype)initWithName:(NSString *)name {
if ((self = [super init]) == nil) { return nil; }
_readableName = name;
_normalizedReadableName = nil;
return self;
}
- (NSString *)normalizedReadableName {
if (_normalizedReadableName == nil) {
_normalizedReadableName = [_readableName normalized];
}
return _normalizedReadableName;
}
- (void)setReadableName:(NSString *)readableName {
_readableName = readableName;
_normalizedReadableName = nil;
}
+(instancetype)cityWithName:(NSString *)name {
return [[self alloc] initWithName:name];
}
@end
同样，这取决于您希望如何进行此处。以它为例。
搜索
indexOfObject:inSortedRange:options:usingComparator:说：
数组中的元素必须已经使用比较器
cmp(这是usingComparator参数(进行排序。如果未对数组进行排序，则结果未定义。
你写道：
数组已根据
readableName属性按字母顺序排序。
但是在您的比较器中，您使用的是lowercaseString.目前还不清楚它是否按小写字符串排序，这可能是另一个问题。否则，结果是未定义的。我们必须对同一个字符串进行操作(排序、比较、hasPrefix等( - 这就是规范化舞蹈的原因。
让我们创建一个示例数组，对其进行洗牌和排序。
NSArray *shuffledCities = [@[
[City cityWithName:@"Čáslav"],
[City cityWithName:@"Čelákovice"],
[City cityWithName:@"Černošice"],
[City cityWithName:@"Černošín"],
[City cityWithName:@"Černovice"],
[City cityWithName:@"Červená Řečice"],
[City cityWithName:@"Červený Kostelec"],
[City cityWithName:@"Česká Kamenice"],
[City cityWithName:@"Česká Lípa"],
[City cityWithName:@"Česká Skalice"],
[City cityWithName:@"Česká Třebová"],
[City cityWithName:@"České Budějovice"],
[City cityWithName:@"České Velenice"],
[City cityWithName:@"Český Brod"],
[City cityWithName:@"Český Dub"],
[City cityWithName:@"Český Krumlov"],
[City cityWithName:@"Český Těšín"],
[City cityWithName:@"Chodová Planá"]
] shuffledArray]; // It's from the GameplayKit.framework
NSArray *sortedCities = [shuffledCities sortedArrayUsingComparator:^NSComparisonResult(City *_Nonnull city1, City *_Nonnull city2) {
return [city1.normalizedReadableName compare:city2.normalizedReadableName];
}];
这里重要的一点是，我们按属性排序normalizedReadableName。
让我们假装prefix是来自您的函数的参数 - 我们还必须规范化它......
NSString *prefix = @"čEsKÝ dub";
NSString *normalizedPrefix = [prefix normalized];
。否则我们的比较器将无法工作：
NSComparisonResult (^comparator)(id _Nonnull, id _Nonnull) = ^(id _Nonnull obj1, id _Nonnull obj2) {
// One has to be City and another one NSString
assert([obj1 isKindOfClass:[NSString class]] || [obj2 isKindOfClass:[NSString class]]);
assert([obj1 isKindOfClass:[City class]] || [obj2 isKindOfClass:[City class]]);
if ([obj1 isKindOfClass:[City class]]) {
return [[obj1 normalizedReadableName] hasPrefix:obj2] ? NSOrderedSame : [[obj1 normalizedReadableName] compare:obj2];
} else {
return [[obj2 normalizedReadableName] hasPrefix:obj1] ? NSOrderedSame : [obj1 compare:[obj2 normalizedReadableName]];
}
};
我看到的另一个问题是，如果obj2City，您的比较器是错误的。比较器期望比较[obj1 compare:obj2]，但在这种情况下，比较器返回[obj2 compare:obj1](obj2City，obj1NSString(。
我们已经修复了比较器，让我们搜索第一个城市：
NSUInteger first = [sortedCities indexOfObject:normalizedPrefix
inSortedRange:NSMakeRange(0, sortedCities.count)
options:NSBinarySearchingFirstEqual
usingComparator:comparator];
if (first == NSNotFound) {
NSLog(@"Prefix "%@" not found", prefix);
return;
}
如果找到，请搜索第二个：
NSUInteger last = [sortedCities indexOfObject:normalizedPrefix
inSortedRange:NSMakeRange(first, sortedCities.count - first)
options:NSBinarySearchingLastEqual
usingComparator:comparator];
// Shouldn't happen as our search range includes the first one
assert(last != NSNotFound);
NSLog(@"Prefix "%@" found", prefix);
NSLog(@" - First %lu: "%@"", (unsigned long)first, [sortedCities[first] readableName]);
NSLog(@" - Last %lu: "%@"", (unsigned long)last, [sortedCities[last] readableName]);
示例输出
所有这些都是正确的。
Prefix "čEsKÝ dub" found
- First 14: "Český Dub"
- Last 14: "Český Dub"
Prefix "Praha" not found
Prefix "ceskÝ" found
- First 13: "Český Brod"
- Last 16: "Český Těšín"
Prefix "cernos" found
- First 2: "Černošice"
- Last 3: "Černošín"