Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
extension String where Element: Strideable {
func fuzzyBinarySearchRecursive(lowerBound: Int = 0, upperBound: Int? = nil, query: Element) -> Int {
let resolvedUpperBound = upperBound ?? count - 1
if lowerBound == resolvedUpperBound {
return lowerBound
}
if lowerBound == resolvedUpperBound - 1 {
// we're in between two elements. pick the one that's closer in value
let a = self[lowerBound]
let b = self[resolvedUpperBound]
let closerToA = query - a < b - query
return closerToA ? lowerBound : resolvedUpperBound
}
let midIdx = lowerBound + (resolvedUpperBound - lowerBound) / 2
let a = self[midIdx]
let b = self[midIdx + 1]
if query - a < b - query {
return fuzzyBinarySearchRecursive(lowerBound: lowerBound, upperBound: midIdx, query: query)
} else {
return fuzzyBinarySearchRecursive(lowerBound: midIdx + 1, upperBound: resolvedUpperBound, query: query)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.