Created
July 8, 2019 20:49
-
-
Save davbeck/027b63c8386f8f5b93b5d96502650273 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 }) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment