package kapitel_14

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

object AuD_14_01_InterpolationSearch_App extends App {

  //a: sortiertes Array mit n Elementen, x gesuchter Wert
  def InterpolationSearch(a: Array[Int], x: Int): Option[Int] = {
    val n = a.length
    var l = 0 //linker Rand des Suchraumes
    var r = n-1 //rechter Rand des Suchraumes
    while (l <= r) {
      if (x < a(l) || x > a(r))
        return None
      if (a(l) == a(r)) {
        if (a(l) == x)
          return Some(l)
        else
          return None
      } else {
        val d_1 = x - a(l)
        val d_2 = a(r) - x
        val m = (d_1 * r + d_2 * l) / (d_1 + d_2)
        if (x == a(m))
          return Some(m)
        if (x < a(m))
          r = m - 1
        else
          l = m + 1
      }
    }
    None
  }

  val a: Array[Int] = Array.tabulate[Int](100)( i => 2*i )

  for (x <- 0 to 100) {
    print(s"$x ")
    println(
      s"${InterpolationSearch(a, x)
        .map(p => s"is at pos $p")
        .getOrElse("not found")}"
    )
  }

}