BinarySearch.swift

// adapted from https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search

/// The result of a binary search.
struct BinarySearchResult<Index> {
	/// The index for the searched key.
	///
	/// Use this to either insert new values while maintaining the sort order of the collection, or to lookup the value if `isPresent` is true.
	var index: Index
	
	/// Whether the key was found in the collection.
	///
	/// When performing a binary search, even if the value is not found in the collection, an index is returned which can be used to insert a new item at the correct location.
	var isPresent: Bool
}

extension Collection where Index: BinaryInteger {
	/// Search for an index for a given key.
	///
	/// Searches through a sorted collection to find the index where the item should be inserted, or already exists.
	///
	/// This method assumes that the collection is already sorted by the given key.
	func binarySearch<Key: Comparable>(for key: Key, using: (Element) -> Key) -> BinarySearchResult<Index> {
		if self.endIndex == self.startIndex {
			return BinarySearchResult(index: startIndex, isPresent: false)
		}
		
		let midIndex = startIndex + (endIndex - startIndex) / Index(exactly: 2)!
		let midKey = using(self[midIndex])
		
		// Is the search key in the left half?
		if midKey > key {
			return self[startIndex..<midIndex].binarySearch(for: key, using: using)
			// Is the search key in the right half?
		} else if midKey < key {
			return self[(midIndex + 1)..<endIndex].binarySearch(for: key, using: using)
			// If we get here, then we've found the search key!
		} else {
			return BinarySearchResult(index: midIndex, isPresent: true)
		}
	}
}

extension Collection where Index: BinaryInteger, Element: Comparable {
	/// Search for an index for a given element.
	///
	/// Searches through a sorted collection to find the index where the item should be inserted, or already exists.
	///
	/// This method assumes that the collection is already sorted.
	func binarySearch(for key: Element) -> BinarySearchResult<Index> {
		return self.binarySearch(for: key, using: { $0 })
	}
}

Example.swift

// maintain an ordered array
var numbers: [Int] = [0,5,9]
for _ in 0..<10 {
	let newValue = Int.random(in: 0..<20)
	let index = numbers.binarySearch(for: newValue).index
	numbers.insert(newValue, at: index)
}

// equivalent to `contains`, but with better performance
numbers.binarySearch(for: 6).isPresent

// sorted dictionary like collection
struct Content {
	var key: String
	var value: Int
}
var content: [Content] = []
for key in ["a", "b", "a", "c"] {
	let newValue = Int.random(in: 0..<20)
	let result = content.binarySearch(for: key, using: { $0.key })
	if result.isPresent {
		content[result.index].value = newValue
	} else {
		content.insert(Content(key: key, value: newValue), at: result.index)
	}
}