1.4.22.md

1.4.22 Binary search with only addition and subtraction. [Mihai Patrascu] Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.

Solution is use Fibonacci numbers sequence. First we need to find number which < than input count. Than use binary search. To find mid index add low to previous Fibonacci number.

func fibonacciSearch(_ input: [Int], target: Int) -> Int {
    var minFib = 1
    var maxFib = 1

    while minFib + maxFib < input.count {
        let sum = minFib + maxFib
        minFib = maxFib
        maxFib = sum
    }

    var lo = 0
    var hi = input.count - 1

    while lo <= hi && minFib >= 0 {
        defer {
            let prev = maxFib - minFib
            maxFib = minFib
            minFib = prev
        }

        let mid = min(minFib + lo, hi)

        guard mid <= hi else { continue }

        let value = input[mid]

        if value < target {
            lo = mid
        } else if value > target {
            hi = mid
        } else {
            return mid
        }
    }

    return -1
}