1.4.20.md

1.4.20 Bitonic search. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array.

Solution is to find bitonic point. If it not target value we search from left of in and if not found - on the right. Solutions based on binary search and pretty straighforward.

First we need to create helper function to find bitonic point:

func findBitonicPoint(_ input: [Int]) -> Int {
    var lo = 0
    var hi = input.count - 1

    while lo < hi {
        let mid = lo + (hi - lo) / 2
        let left = mid - 1
        let right = mid + 1
        if left < 0 || right >= input.count { return -1 }

        if input[mid] > input[left] && input[mid] > input[right] { return mid }
        else if input[mid] < input[left] { hi = mid }
        else if input[mid] < input[right] { lo = mid + 1 }
        else { return -1 }
    }

    return -1
}

Than another two helper functions for using binary search in ascending and descending subsequences:

func ascendingBinarySearch(_ input: [Int], lo: Int, hi: Int, target: Int) -> Int {
    var lo = lo
    var hi = hi
    while lo <= hi {
        let mid = lo + (hi - lo) / 2

        if input[mid] < target { lo = mid + 1 }
        else if input[mid] > target { hi = mid - 1}
        else { return mid }
    }

    return -1
}

func descendingBinarySearch(_ input: [Int], lo: Int, hi: Int, target: Int) -> Int {
    var lo = lo
    var hi = hi
    while lo <= hi {
        let mid = lo + (hi - lo) / 2

        if input[mid] > target { lo = mid + 1 }
        else if input[mid] < target { hi = mid - 1}
        else { return mid }
    }

    return -1
}

And finally main function which combile all of helper functions:

func bitonicSearch(_ input: [Int], target: Int) -> Int {
    guard input.count > 2 else { return -1 }

    let bp = findBitonicPoint(input)
    if bp == -1 || input[bp] == target { return bp }

    let index = ascendingBinarySearch(input, lo: 0, hi: bp - 1, target: target)
    return index != -1 ? index : descendingBinarySearch(input, lo: bp + 1, hi: input.count - 1, target: target)
}