Swift/Array.containsはO(n) だが、Range系はO(1)

環境

code:sh

$swift --version

swift-driver version: 1.82.2 Apple Swift version 5.9 (swiftlang-5.9.0.114.10 clang-1500.0.29.1)

Target: arm64-apple-macosx14.0

モチベーション

Array.containsの時間計算量がO(n)ということは知っていたが、Range系のcontainsは違うことを知らなかったのでメモ

hr.icon

Array.contains

Complexity

O(n), where n is the length of the sequence.

Range.contains

時間計算量についての言及はない

code:swift

// ClosedRange

@inlinable

public func contains(_ element: Bound) -> Bool {

return element >= self.lowerBound && element <= self.upperBound

}

範囲はソート済み配列と見なせるため、下端と上端の範囲内に収まるかを見れば良い。O(1)となる