objective-c - 优化数组搜索，通过比较 Objective C 中的 2 个字符串进行搜索

Question

我有一个从地址簿中检索到的联系人列表，存储在 MutableArray 联系人列表中。每个联系人都是一个对象，它具有诸如“contactName、contactImage...等”的属性。

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0),^{
    //getAllContacts is a method which returns a Mutable array of Objects
    self.contactList = [NSMutableArray arrayWithArray:[instance getAllContacts]];

    //groupLetterToLoad could be "DEF"
    for(int j=0; j<self.groupLetterToLoad.length;j++) { 
        //1st iteration D, 2nd iteration E and 3rd iteration F
        NSString *testChar = [NSString stringWithFormat:@"%c",[self.groupLetterToLoad characterAtIndex:j]];
        //check D,E,F with contact name property's first letter of the contact list array
        for(int i=0;i<self.contactList.count;i++) {
            NSString *firstChar =[[[self.contactList objectAtIndex:i] contactName] substringToIndex:1];
            if([testChar isEqualToString: firstChar]) {
                pos=i; //retrieve the index of the matched position
                break;
            }
        }
        if(pos!=-1) break;
    }
});

现在这有两个 for 循环(时间 O(n^2))。这里的缺点是，如果 groupLetterToLoad 是“WXYZ”，那么比较将从 W 和 A 开始到 W 和 Z。我怎么能优化了吗？

Answer 1

按 contactName 对数组进行排序并执行半间隔搜索将大大降低复杂性，如果可以避免每次搜索时都排序(提示:保持 [instance getAllContacts] 排序).

http://rosettacode.org/wiki/Binary_search#Objective-C - 这是一个起点。您可以将 compare: 替换为您的第一个字符比较。