哪個Swift收集協議要擴展以添加二進制搜索

我想實現一些二進制搜索，就像對隨機訪問（恆定時間）的排序元素集合進行操作的函數一樣，並且支持索引算術（用於派生一個mid點）。我可以將這些方法添加爲擴展名或Array。但是，我更願意將它們添加到支持必要功能的更通用的協議，以便我的擴展可以更廣泛地使用。哪個Swift收集協議要擴展以添加二進制搜索

我應該使用哪種協議，以及我將來如何去尋找這樣的協議？我搜索了「Swift收集協議層次結構」和類似的內容，除了各種紅鯡魚之外，我還沒有發現任何有用的東西。

來源

2017-05-31 Benjohn

您*可以*實現它爲任意集合（例如：https://stackoverflow.com/a/40226976/1187415）。 [RandomAccessCollection]（https://developer.apple.com/reference/swift/randomaccesscollection）保證您可以在O（1）時間內移動索引。 –

這是一個開始的好地方：https：//www.skilled.io/u/playgroundscon/sequence-and-collection-swift –

對於你需要找到兩個指數位置之間的「中點」的二進制搜索，這是可能的任何Collection，因爲其相關IndexDistance要求是一個SignedInteger。

一種可能的實現（從https://stackoverflow.com/a/40226976/1187415採取）是

extension Collection { 

    func binarySearch(predicate: (Iterator.Element) -> Bool) -> Index { 
     var low = startIndex 
     var high = endIndex 
     while low != high { 
      let mid = index(low, offsetBy: distance(from: low, to: high)/2) 
      if predicate(self[mid]) { 
       low = index(after: mid) 
      } else { 
       high = mid 
      } 
     } 
     return low 
    } 
}

這裏distance(from:to:)返回IndexDistance可以除以2，因爲它符合SignedInteger（並因此IntegerArithmetic），其結果可用於在index(_:offsetBy:)。

這兩種方法的文檔指出複雜性是

O（1）如果集合符合RandomAccessCollection;否則，O（n），其中n是n的絕對值。

所以，如果你想保證它僅在收集針對移動指標和測量距離是O（1）操作中使用，你可以實現它爲RandomAccessCollection 的延伸。

或者你實現它作爲Collection的擴展，以便它可以被普遍使用。當呼叫RandomAccessCollection時，它將是「快速」（在上述意義上），否則可能「慢」。

來源

2017-05-31 18:20:24

哪個Swift收集協議要擴展以添加二進制搜索

回答

相關問題