###### tags: `ADA 2.5` `Bitonic Champion Problem`
# ADA 2.5 Bitonic Champion Problem

Input: A bitonic sequence A[1], A[2],..., A[n] of distinet positive integers.
Output: the index i with 1 < i ≤ n such that

已知性質
1.山峰之前遞增，山峰之後遞減
The bitonic sequence means "increasing before the champion and decreasing after the champion”
2.只有一座山峰

Only one champion.

暴力解法：

func findBitonicChampion(_ bitonicArray: [Int]) -> Int {
    var champion = 0

    for indexElement in bitonicArray {
        if champion < indexElement {
            champion = indexElement
        } else if champion > indexElement {
            break
        } 
    }
    
    return champion
}

但這也意味著，這個解法的時間複雜度為log(n)
這顯然不是我們要的

## 第一解：


func findBitonicChampion(_ bitonicArray: [Int]) -> Int {
    guard bitonicArray.count > 1 else {
        return bitonicArray.first ?? 0
    }
    
    var leftChampion = 0
    var rightChampion = 0
    var leftNowIndex = 0
    var rightNowIndex = 0
    let middleCount = bitonicArray.count / 2
    
    repeat {
        if bitonicArray[leftNowIndex] < bitonicArray[leftNowIndex + 1] {
            leftChampion = bitonicArray[leftNowIndex + 1] 
        }
        leftNowIndex + 2
    } while leftNowIndex == middleCount
    
    repeat {
        if bitonicArray[rightNowIndex] < bitonicArray[rightNowIndex - 1] {
            rightChampion = bitonicArray[rightNowIndex - 1] 
        }
        rightNowIndex - 2
    } while rightNowIndex == middleCount + 1
    

    return leftChampion > rightChampion ? leftChampion : rightChampion
}

第一解釋提供了Lower bound的思路，左右對切後，所執行Ｔ的總時下降至T([n/2])＊２＋b，這依舊意味著，還有更優良的解法，我們可以減少不必要的比較時間．

## 更優解，利用山峰性質作為定位：
最簡單的就是對切後，我們可以考慮直接對中二分

必須考慮山峰位置問題，有時候山峰不一定在中央：

所以以中央的indx為起始，根據index的座右來判斷現在是上下坡

上坡，則是左<中<右
下坡，則是左>中>右
山頂，則是左<中>右

func findBitonicChampion(_ bitonicArray: [Int]) -> Int {
    guard bitonicArray.count > 1 else {
        return bitonicArray.first ?? 0
    }
    
    guard bitonicArray.count > 3 else {
        return bitonicArray[1]
    }

    //山峰的特性：左右都小於他
    var nowIndex = bitonicArray.count / 2
    
    repeat {
        if bitonicArray[nowIndex] > bitonicArray [nowIndex + 1] &&  bitonicArray [nowIndex - 1] > bitonicArray[nowIndex] {  
            nowIndex = nowIndex /2
        } else if bitonicArray[nowIndex] < bitonicArray [nowIndex + 1] &&  bitonicArray [nowIndex - 1] < bitonicArray[nowIndex] { 
            nowIndex = nowIndex + nowIndex/2
        }
    } while bitonicArray[nowIndex] > bitonicArray [nowIndex - 1] && bitonicArray[nowIndex] > bitonicArray [nowIndex - 1] 
    
    return bitonicArray[nowIndex] 
}

這個做法等於少了一次T([n/2])，時間複雜度可下降至T([n/2])