二進制搜索

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來查找插入新元素以保持列表排序的索引。