使用indexOfObject:inSortedRange:options:usingComparator:二分搜索筛选NSArray异常排查

你的核心问题在于误用了indexOfObject:inSortedRange:options:usingComparator:的设计逻辑，以及比较器没有满足二分搜索所需的严格全序关系要求。让我拆解问题并给出可行的修复方案：

为什么当前代码失效？ #

1. 方法定位错误
   indexOfObject:...的设计目标是查找数组中与目标对象严格相等的元素位置，而你传入的目标对象是NSString类型的前缀，数组元素却是City对象。你的比较器把“城市名包含前缀”定义为NSOrderedSame，但这并非真正的“相等”——二分搜索算法无法在这种模糊的“相等”关系下正确收敛，最终只能返回NSNotFound（也就是你看到的long最大值）。

2. 比较器逻辑不符合二分搜索要求
   二分搜索的比较器必须能对任意两个元素返回明确的排序关系（NSOrderedAscending/NSOrderedDescending/NSOrderedSame），且这个关系必须是全序的（即任意两个元素都能明确比较大小）。你的逻辑中，只要前缀匹配就返回NSOrderedSame，破坏了这种全序性，导致算法无法正确缩小搜索范围。

正确的实现思路 #

既然数组是按readableName排序的，我们可以利用前缀匹配的特性：所有以prefix开头的字符串，必然大于等于prefix的小写形式，且小于prefix的“后继字符串”（比如prefix是"Ams"，后继字符串就是"Amt"——这是所有以"Ams"开头的字符串的上限）。

基于这个特性，我们可以手动实现二分搜索来找到两个关键边界：

• 左边界：第一个满足readableName >= prefix且前缀匹配的元素索引
• 右边界：第一个满足readableName >= 后继字符串的元素索引，再减1就是最后一个匹配元素的索引

完整代码实现 #

1. 辅助方法：生成前缀的后继字符串 #

+ (NSString *)successorStringForPrefix:(NSString *)prefix {
    if (prefix.length == 0) return @"";
    NSMutableString *succ = [prefix mutableCopy];
    NSInteger lastIndex = succ.length - 1;
    unichar lastChar = [succ characterAtIndex:lastIndex];
    // 将最后一个字符的ASCII值加1，生成后继字符串
    [succ replaceCharactersInRange:NSMakeRange(lastIndex, 1) 
                       withString:[NSString stringWithCharacters:&(lastChar+1) length:1]];
    return succ;
}

2. 查找左边界（第一个匹配前缀的元素） #

+ (long)findLeftBoundForPrefix:(NSString *)prefix inCityArray:(NSArray *)array {
    NSString *lowerPrefix = [prefix lowercaseString];
    long low = 0;
    long high = array.count;

    while (low < high) {
        long mid = low + (high - low)/2; // 避免溢出
        City *city = array[mid];
        NSString *cityNameLower = [city.readableName lowercaseString];
        
        NSComparisonResult result = [cityNameLower compare:lowerPrefix];
        if (result == NSOrderedAscending) {
            // 城市名比prefix小，左边界在右侧
            low = mid + 1;
        } else {
            // 城市名大于等于prefix，左边界在左侧或当前位置
            high = mid;
        }
    }

    // 验证找到的位置是否真的匹配前缀，防止无匹配的情况
    if (low < array.count) {
        City *city = array[low];
        if ([[city.readableName lowercaseString] hasPrefix:lowerPrefix]) {
            return low;
        }
    }
    return NSNotFound;
}

3. 查找右边界（最后一个匹配前缀的元素） #

+ (long)findRightBoundForPrefix:(NSString *)prefix inCityArray:(NSArray *)array {
    NSString *lowerSuccessor = [[self successorStringForPrefix:prefix] lowercaseString];
    long low = 0;
    long high = array.count;

    while (low < high) {
        long mid = low + (high - low)/2;
        City *city = array[mid];
        NSString *cityNameLower = [city.readableName lowercaseString];
        
        NSComparisonResult result = [cityNameLower compare:lowerSuccessor];
        if (result == NSOrderedAscending) {
            // 城市名比后继字符串小，右边界在右侧
            low = mid + 1;
        } else {
            // 城市名大于等于后继字符串，右边界在左侧或当前位置
            high = mid;
        }
    }

    // 右边界是第一个大于等于后继字符串的位置，所以最后一个匹配项是low-1
    long rightBound = low - 1;
    if (rightBound >= 0) {
        City *city = array[rightBound];
        if ([[city.readableName lowercaseString] hasPrefix:[prefix lowercaseString]]) {
            return rightBound;
        }
    }
    return NSNotFound;
}

4. 整合方法获取范围 #

+ (FilterRange *)findRangeHeadAndTailForPrefix:(NSString *)prefix inCityArray:(NSArray *)array {
    FilterRange *result = [[FilterRange alloc] init];
    result.startIndex = [self findLeftBoundForPrefix:prefix inCityArray:array];
    
    if (result.startIndex != NSNotFound) {
        result.endIndex = [self findRightBoundForPrefix:prefix inCityArray:array];
    } else {
        result.endIndex = NSNotFound;
    }
    
    return result;
}

额外说明 #

• 手动实现二分搜索虽然比系统方法多写了代码，但能精准控制边界逻辑，完全适配前缀匹配的场景。
• 后继字符串的生成逻辑简单可靠，能覆盖绝大多数城市名的场景（即使是类似"ZZZ"的极端情况，生成的"ZZ["也能正确作为上限）。
• 每次边界查找后都做了前缀验证，避免数组中无匹配项时返回错误索引。

内容的提问来源于stack exchange，提问作者Sepehrom