1.4.10.md

1.4.10 Modify binary search so that it always returns the element with the smallest index that matches the search element (and still guarantees logarithmic running time).

Solution: instead of return value when we found match compare it against another search on lesser range and return min index.

func binarySearch<T: Comparable>(in array: [T], value: T, range: Range<Int>) -> Int {
    guard range.lowerBound < range.upperBound else { return Int.max }

    let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

    if value > array[midIndex] { return binarySearch(in: array, value: value, range: midIndex + 1..<range.upperBound) }
    if value < array[midIndex] { return binarySearch(in: array, value: value, range: range.lowerBound..<midIndex) }
    else { return min(midIndex, binarySearch(in: array, value: value, range: range.lowerBound..<midIndex)) }
}