Binary Search

BinarySearch.swift

import Foundation

func binarySearch<T: Comparable>(_ A: [T], key: T, _low: Int = 0, _high: Int = 0) -> Int? {
    var low = _low
    var high = _high
    if _high == 0 {
        high = A.count
    }
    while low < high {
        let mid = low + (high - low) / 2
        if A[mid] == key {
            return mid
        } else if A[mid] < key {
            low = mid + 1
        } else {
            high = mid
        }
    }
    return nil
}

let numbers = [3, 99, 66, 77, 32, 2, 6, 49, 50, 20, 95]
let words = ["b", "c", "a", "z", "y", "w", "o", "t"]

let numbers2 = numbers.sorted()
let words2 = words.sorted()

print(numbers2)
print(binarySearch(numbers2, key: 2)!)
print(binarySearch(numbers2, key: 99)!)
print(binarySearch(numbers2, key: 100))

print(words2)
print(binarySearch(words2, key: "a")!)
print(binarySearch(words2, key: "z")!)
print(binarySearch(words2, key: "A"))

/*
[2, 3, 6, 20, 32, 49, 50, 66, 77, 95, 99]
0
10
nil

["a", "b", "c", "o", "t", "w", "y", "z"]
0
7
nil
*/