/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 12, Teilen und Herrschen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_12_01_CountTH {

    static func countTH(_ a: [Int], _ l:Int, _ r: Int, _ x: Int) -> Int {
        if l == r {
            return a[l] == x ? 1 : 0
        } else {
            let m: Int = Int(ceil((Double(l) + Double(r)) / 2.0))
            let c_l = countTH(a, l, m - 1, x)
            let c_r = countTH(a, m, r, x)
            return c_l + c_r
        }
    }

    static let a: [Int] = [6,5,3,4,3,4,3,5,2,4,6,5,2,5,4,5,6,6,6,6]

    static func run () {
        for x in 1 ... 7 {
            print("\(x) -> \(countTH(a, 0, a.count-1, x))")
        }
    }

}