package kapitel_12

/**
 * 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
 */

object AuD_12_01_CountTH_App extends App {

  /**
   * Wie oft kommt ein Wert in einem Array vor
   * @param a Der Array
   * @param l Linke Grenze
   * @param r Rechte Grenze
   * @param x Der gesuchte Wert
   * @return Anzahl der Vorkommen von x in a(l .. r)
   */
  def countTH(a: Array[Int], l:Int, r: Int, x: Int): Int =
    if (l == r) {
      if (a(l) == x) 1 else  0
    } else {
      val m = Math.ceil((l.toDouble + r.toDouble)/2.0).toInt
      val c_l = countTH(a, l, m-1, x)
      val c_r = countTH(a, m, r, x)
      c_l + c_r
    }

  val a: Array[Int] = Array.tabulate[Int](25)( i => i % 3)

  println(s"[${a.mkString(",")}]")

  println(s"number of 0 in a: ${countTH(a, 0, a.length-1, 0)}") // 9
  println(s"number of 1 in a: ${countTH(a, 0, a.length-1, 1)}") // 8
}