NearestKeyDictionary.swift

struct NearestKeyDictionary<Key: Comparable & Hashable, Value: Equatable>: ExpressibleByDictionaryLiteral {
    // MARK: Type aliases

    typealias Values = Dictionary<Key, Value>.Values

    // MARK: Public properties

    var allValues: Values {
        return dictionary.values
    }

    private(set) var allKeys: SortedArray<Key>

    // MARK: Initializers

    init(_ dictionary: [Key:Value]) {
        self.dictionary = dictionary
        self.allKeys = SortedArray(self.dictionary.keys)
    }

    init(dictionaryLiteral elements: (Key, Value)...) {
        self.dictionary = [:]

        for (key, value) in elements {
            self.dictionary[key] = value
        }

        self.allKeys = SortedArray(self.dictionary.keys)
    }

    // MARK: Public methods

    func indexOfNearestKey(to key: Key) -> Int? {
        let allKeys = self.allKeys
        let index = allKeys.insertionIndex(of: key)

        guard index >= allKeys.startIndex && index < allKeys.endIndex else {
            return nil
        }

        return index
    }

    func nearestKey(to key: Key) -> Key? {
        guard let index = self.indexOfNearestKey(to: key) else {
            return nil
        }

        return self.allKeys[index]
    }

    func objectNear(key: Key) -> Value? {
        guard let index = indexOfNearestKey(to: key) else {
            return nil
        }

        let key = allKeys[index]

        return self.dictionary[key]
    }

    subscript(_ key: Key) -> Value? {
        get {
            return objectNear(key: key)
        }
        set {
            self.dictionary[key] = newValue
            self.allKeys = SortedArray(self.dictionary.keys)
        }
    }

    // MARK: Private properties

    private var dictionary: [Key:Value]
}

extension NearestKeyDictionary: Equatable {
    static func ==(lhs: NearestKeyDictionary<Key, Value>, rhs: NearestKeyDictionary<Key, Value>) -> Bool {
        return lhs.dictionary == rhs.dictionary
    }
}

func testObjectForKey() {
    let (key1, key2) = (20, 30)

    let dictionary = [
        10  : "A",
        key1: "B",
        key2: "C",
        40  : "D",
    ]

    let nearestDictionary = NearestKeyDictionary(dictionary)

    assert(dictionary[key1] == nearestDictionary[key1])
    assert(dictionary[key2] == nearestDictionary[key2])
}

testObjectForKey()

func testObjectNearKey() {
    let nearestDictionary: NearestKeyDictionary = [
        10: "A",
        20: "B",
        30: "C",
        40: "D",
    ]

    assert(20 == nearestDictionary.nearestKey(to: 11))
    assert(30 == nearestDictionary.nearestKey(to: 29))
    assert(30 == nearestDictionary.nearestKey(to: 30))
}

testObjectNearKey()

SortedArray.swift

public struct SortedArray<E: Comparable> {
    var elements: [E]

    public init(_ elements: [E]) {
        self.elements = elements.sorted()
    }

    public init<S: Sequence>(_ elements: S) where S.Iterator.Element == E {
        self.elements = Array(elements).sorted()
    }

    // Mark: Public

    public mutating func insert(_ element: E) {
        let index = insertionIndex(of: element)
        elements.insert(element, at: index)
    }

    public func insertionIndex(of element: E) -> Int {
        var (startIndex, endIndex) = (elements.startIndex, elements.endIndex)

        while startIndex < endIndex {
            let middle = startIndex + (endIndex - startIndex) / 2

            if elements[middle] < element {
                startIndex = middle + 1
            } else {
                endIndex = middle
            }
        }

        return startIndex
    }

    public func contains(_ element: E) -> Bool {
        return index(of: element) != nil
    }

    // MARK: Private

    private func index(of element: E) -> Int? {
        let index = insertionIndex(of: element)

        guard (index != endIndex && self[index] == element) else {
            return nil
        }

        return index
    }
}

extension SortedArray: Collection {
    public typealias Indices = DefaultRandomAccessIndices<SortedArray<E>>
    public typealias Element = E

    public var startIndex: Int {
        return elements.startIndex
    }

    public var endIndex: Int {
        return elements.endIndex
    }

    public subscript(index: Int) -> E {
        return elements[index]
    }

    public func index(after i: Int) -> Int {
        return elements.index(after: i)
    }

    public func flatMap(_ transform: (E) throws -> E?) rethrows -> SortedArray<E> {
        return try SortedArray(elements.flatMap(transform))
    }
}

extension SortedArray: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: E...) {
        self.elements = []

        for value in elements {
            self.insert(value)
        }
    }
}

extension SortedArray: BidirectionalCollection {
    public func index(before i: Int) -> Int {
        return elements.index(before: i)
    }
}

extension SortedArray: RandomAccessCollection {

}

extension SortedArray: Equatable {
    public static func ==(lhs: SortedArray, rhs: SortedArray) -> Bool {
        guard lhs.count == rhs.count else {
            return false
        }

        for (l, r) in zip(lhs, rhs) where l != r {
            return false
        }

        return true
    }
}