package kapitel_12

import scala.language.implicitConversions
import scala.util.Sorting

/**
 * 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_02_BinarySearch_App extends App {

  /**
   * Binaere Suche in einem Array
   * @param a  sortiertes Array mit n Elementen
   * @param x  gesuchter Wert
   * @return   Position von x oder None
   */
  def BinarySearch(a: Array[Int], x: Int): Option[Int] = {
    var l = 0
    var r = a.length-1
    while (l <= r) {
      val m = (l + r)/2
      if (x == a(m))
        return Some(m)
      if (x < a(m))
        r = m-1
      else
        l = m+1
    }
    None
  }

  // oder generisch:
  def BinarySearchG[A](a: Array[A], x: A)(implicit ordering: Ordering[A] ): Option[Int] = {
    implicit def toOrdered(a:A): Ordered[A] = Ordered.orderingToOrdered(a)
    var l = 0
    var r = a.length-1
    while (l <= r) {
      val m = (l + r)/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)
    println(s"$x => pos: ${BinarySearch(a, x).getOrElse("not found")}")

  // das Gleiche mit absteigender Sortierung
  Sorting.stableSort(a)((x,y)=> y-x)
  for (x <- 0 to 100)
    println(s"$x => pos: ${BinarySearchG(a, x)( (x,y)=> y-x ) . getOrElse("not found")}")


}