Last active
August 18, 2017 07:21
-
-
Save qhhonx/33d954821de917b8b6b04d10a106fc30 to your computer and use it in GitHub Desktop.
Implementations of lowerBound and upperBound for Array.
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
// Write some awesome Swift code, or import libraries like "Foundation", | |
// "Dispatch", or "Glibc" | |
extension Array where Element: Comparable { | |
func lowerBound(in range: CountableRange<Index>, for value: Element) -> Index { | |
return lowerBound(in: range, for: value, by: <) | |
} | |
func lowerBound(for value: Element) -> Index { | |
return lowerBound(in: startIndex ..< endIndex, for: value, by: <) | |
} | |
func upperBound(in range: CountableRange<Index>, for value: Element) -> Index { | |
return lowerBound(in: range, for: value, by: <=) | |
} | |
func upperBound(for value: Element) -> Index { | |
return lowerBound(in: startIndex ..< endIndex, for: value, by: <=) | |
} | |
} | |
extension Array { | |
func upperBound(for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index { | |
return lowerBound(in: startIndex ..< endIndex, for: value, by: { (lhs, rhs) -> Bool in !areInIncreasingOrder(rhs, lhs) }) | |
} | |
func upperBound(in range: CountableRange<Index>, for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index { | |
return lowerBound(in: startIndex ..< endIndex, for: value, by: { (lhs, rhs) -> Bool in !areInIncreasingOrder(rhs, lhs) }) | |
} | |
func lowerBound(for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index { | |
return lowerBound(in: startIndex ..< endIndex, for: value, by: areInIncreasingOrder) | |
} | |
func lowerBound(in range: CountableRange<Index>, for value: Element, by areInIncreasingOrder: (Element, Element) -> Bool) -> Index { | |
precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex) | |
var count = range.count | |
var lowerBound = range.lowerBound | |
while count > 0 { | |
let step = count / 2 | |
let iter = lowerBound + step | |
if areInIncreasingOrder(self[iter], value) { | |
lowerBound = iter + 1 | |
count -= step + 1 | |
} else { | |
count = step | |
} | |
} | |
return lowerBound | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
results of above test codes: