[Swift Algorithm] Binary search
2016-07-16 本文已影响30人
sunlitamo
func binarySearch(a: [Int], key: Int, range: Range<Int>) -> Int? {
if range.startIndex >= range.endIndex {
// If we get here, then the search key is not present in the array.
return nil
} else {
// Calculate where to split the array.
let midIndex = range.startIndex + (range.endIndex - range.startIndex) / 2
// Is the search key in the left half?
if a[midIndex] > key {
return binarySearch(a, key: key, range: range.startIndex ..< midIndex)
// Is the search key in the right half?
} else if a[midIndex] < key {
return binarySearch(a, key: key, range: midIndex + 1 ..< range.endIndex)
// If we get here, then we've found the search key!
} else {
print(midIndex)
return midIndex
}
}
}