二进制搜索

Question

我不明白的阵列方法indexOfObject:inSortedRange:options:usingComparator:

更具体地说，indexOfObject财产。

根据文档传递的值应该是An object for which to search in the array.但这没有任何意义。如果我已经有了对象的引用，为什么我会在数组中搜索它？这是否意味着对象类型？

我有一个对象数组，我拥有的是这些对象的属性。即。我有一系列的汽车，当我有车号为12345时，我需要找到车对象。

我会传入indexOfObject属性的方法么？这里是我想要

MyCarObject *searchObject; 
    NSUInteger findIndex = [sortedArray indexOfObject:searchObject 
             inSortedRange:searchRange 
              options:NSBinarySearchingFirstEqual 
            usingComparator:^(id obj1, id obj2) 
           { 
           return [obj1 compare:obj2]; 
           }]; 

，但是这显然是不会得到一个基于ID的对象..它看起来像它要给我的财产的索引我已经有一个参考，这似乎毫无意义....

如果这不是正确的方法，那么我应该使用什么？我需要在对象数组上使用二进制搜索并提取对该对象的引用。我拥有的只是一个财产来比较。

Answer 1

此方法返回给您给定数组中的对象的索引，有时这可能非常有用。使用isEqual:方法（默认情况下比较指针）比较阵列中的对象。这就是该方法没有机会知道您希望使用您的某些自定义属性进行比较的原因。

对于你自己的财产的数组中查找特定对象，利用可以利用

• NSArray S分析- (NSArray *)filteredArrayUsingPredicate:和相应的NSPredicate（有很多的问题，对SO和教程这些）
• 自己的循环比较任何你想要的属性与任何值（与您通过搜索车ID在你的情况下，物体的车ID）

Answer 2

这是可能会将这个API用来做你想做的事，尽管我并不真正提倡这种方法。如果你要搜索的关键，将与元素一起传递到比较器通过被比较反对。但是，传递这些参数的顺序会发生变化，所以您需要在运行时检查比较器参数的类，以区分它们并执行比较。

- (BWCProductCategory *)categoryForID:(NSNumber *)ID categories:(NSArray *)categories { 
    NSRange searchRange = NSMakeRange(0, categories.count); 
    NSUInteger index = [categories indexOfObject:ID 
            inSortedRange:searchRange 
             options:NSBinarySearchingFirstEqual 
           usingComparator:^NSComparisonResult(id obj1, id obj2) { 
            if ([obj1 isKindOfClass:[BWCProductCategory class]]) { 
             return [[(BWCProductCategory *)obj1 categoryID] compare:obj2]; 
            } else { 
             return [obj1 compare:[(BWCProductCategory *)obj2 categoryID]]; 
            } 
           }]; 

    return (index == NSNotFound) ? nil : categories[index]; 
} 

这并不功能，但是感觉很别扭，加上执行大型搜索时我没有信心对性能的影响（虽然这肯定是仍然小于一个O（n）的搜索）。也许你可以在隐藏混杂因素的基础上构建一个更好的方法。

Answer 3

我创建了一个延伸到斯威夫特的Array使以这种方式使用雨燕非常干净。

import Foundation 

extension Array where Element: AnyObject { 

    public func indexOfObject<T: AnyObject>(obj: T, options opts: NSBinarySearchingOptions, usingComparator cmp: (T, Element) -> NSComparisonResult) -> Int { 
     return (self as NSArray).indexOfObject(obj, inSortedRange: NSRange(0..<count), options: opts, usingComparator: { (a: AnyObject, b: AnyObject) -> NSComparisonResult in 
      if a === obj { 
       return cmp(a as! T, b as! Element) 
      } else { 
       var result = cmp(b as! T, a as! Element) 

       if result == .OrderedDescending { 
        result = .OrderedAscending 
       } else if result == .OrderedAscending { 
        result = .OrderedDescending 
       } 

       return result 
      } 
     }) 
    } 
} 

下面是一个例子用法：

class ItemWithProperty { 
    var property: Int 

    init(property: Int) { 
     self.property = property 
    } 
} 

let listOfItems = [ItemWithProperty(property: 1), 
    ItemWithProperty(property: 20), 
    ItemWithProperty(property: 30), 
    ItemWithProperty(property: 45), 
    ItemWithProperty(property: 45), 
    ItemWithProperty(property: 45), 
    ItemWithProperty(property: 60), 
    ItemWithProperty(property: 77), 
] 

let indexOf20 = listOfItems.indexOfObject(20, options: .FirstEqual) { number, item in 
    number.compare(item.property) 
} 
// returns 1 

let indexOf25 = listOfItems.indexOfObject(25, options: .FirstEqual) { number, item in 
    number.compare(item.property) 
} 
indexOf25 == NSNotFound 
// comparison is true, number not found 

let indexOfFirst45 = listOfItems.indexOfObject(45, options: .FirstEqual) { number, item in 
    number.compare(item.property) 
} 
// returns 3 

let indexOfLast45 = listOfItems.indexOfObject(45, options: .LastEqual) { number, item in 
    number.compare(item.property) 
} 
// returns 5 

let indexOf77 = listOfItems.indexOfObject(77, options: .FirstEqual) { number, item in 
    number.compare(item.property) 
} 
// returns 7 

Answer 4

的compare:方法（其使用的是你二进制搜索比较器）指根据目的不同的事情。例如，NSString，实现比较为词法比较。因此，如果您的排序为NSArray的NSString，那么您将返回的是与输入字符串匹配的字符串列表中的索引（如果不在数组中，则为NSNotFound）。

对于您的对象类型（MyCarObject），你会实现你的compare:定义确定的MyCarObject S中的相对顺序。然后，您可以构造一个MyCarObject的新实例，并使用此方法确定是否有一个等效对象（由compare:确定）已经在列表中。

请注意，此方法执行二分搜索，因此必须使用您用于搜索的相同比较器对数组进行排序。您可以使用NSBinarySearchingInsertionIndex来查找插入新元素以保持列表排序的索引。