Binary Search by KeyPath

KeyPathBinarySearch.swift

import UIKit
import XCTest

extension Array {
    /// Determine if an `Array` contains an element by a specific property using a Binary Search Algorithm
    /// - Parameters:
    ///   - searchItem: Element with property to search for
    ///   - keyPath: KeyPath of property to search for
    ///   - isSorted: Whether or not the `Array` is ordered. Default value is `true`
    /// - Returns: `true` if `Array` contains `searchItem` KeyPath, `false` if it does not
    func binarySearchContains<T: Comparable>(_ searchItem: Element, by keyPath: KeyPath<Element, T>, isSorted: Bool = true) -> Bool {
        guard !self.isEmpty else { return false }
        var copy = self
        if !isSorted {
            copy = copy.sorted(by: { $0[keyPath: keyPath] < $1[keyPath: keyPath] })
        }
        var lowerIndex = 0
        var upperIndex = count - 1
        repeat {
            let currentIndex = (lowerIndex + upperIndex) / 2
            if copy[currentIndex][keyPath: keyPath] == searchItem[keyPath: keyPath] {
                return true
            }
            guard lowerIndex < upperIndex else { return false }
            if copy[currentIndex][keyPath: keyPath] > searchItem[keyPath: keyPath] {
                upperIndex = currentIndex - 1
            } else {
                lowerIndex = currentIndex + 1
            }

        } while true
    }
}

class BinarySearchContainsTests: XCTestCase {
    struct Foo {
        let bar: Int
        var baz: Int
        
        init(_ value: Int) {
            bar = value
            baz = value + 1
        }
    }
        
    let searchArray = (1...500).map(Foo.init)
    
    func testContains() {
        var foo = Foo(500)
        foo.baz = 750

        XCTAssertTrue(searchArray.binarySearchContains(foo, by: \.bar))
        XCTAssertFalse(searchArray.binarySearchContains(foo, by: \.baz))
    }
    
    func testSortAndContains() {
        let searchUnorderedArray = searchArray.shuffled()
        var foo = Foo(200)
        foo.baz = 1000
        
        XCTAssertTrue(searchUnorderedArray.binarySearchContains(foo, by: \.bar, isSorted: false))
        XCTAssertFalse(searchUnorderedArray.binarySearchContains(foo, by: \.baz, isSorted: false))
    }
}

BinarySearchContainsTests.defaultTestSuite.run()