// sl-4-DHBW-Inf2 : Suchen in Arrays
// Lineare Suche : Suche von vorne bis hinten (selbst programmieren)
// Binäre Suche : Teste in der "Mitte", dann links oder rechts weiter
// Interpolationssuche : Suche, wo es vermutlich liegt

// Übungsaufgaben: Umschreiben mit while-Schleifen
// Was passiert bei Kombination von Interpol mit Binsearch2?
// Experimenteller Vergleich der Suchverfahren:
// Anzahl der Schlüssel-Vergleiche Minimum, Maximum, Mittel?

#include "intervallschachtelung.h"
#include <iostream>
using namespace std;

bool binsearch1 (int a[], const int gesucht, const int von, const int bis) {
  cout << von << bis << endl; // nur zum Testen
  if (bis>=von) {
    int mitte=(von+bis)/2;
    if (a[mitte]==gesucht) {
      return true;
    } else if (a[mitte]>gesucht) {
      return binsearch1(a,gesucht,von,mitte-1);
    } else {
      return binsearch1(a,gesucht,mitte+1,bis);
    }
  } else return false;
}

bool binsearch2 (int a[], const int gesucht, const int von, const int bis) {
  cout << von << bis << endl; // nur zum Testen
  if (bis>von) {
    int mitte=(von+bis)/2;
    if (a[mitte]<gesucht) {
      return binsearch2(a,gesucht,mitte+1,bis);
    } else {
      return binsearch2(a,gesucht,von,mitte);
    }
  } else {
    return a[von]==gesucht;
  }
}

bool interpol1 (int a[], const int gesucht, const int von, const int bis) {
  // cout << von << bis << endl; // nur zum Testen
  if (bis>von) {
    int mitte=von+(gesucht-a[von])*(bis-von)/(a[bis]-a[von]);
    if (mitte<von || mitte>bis) { // außerhalb des erlaubten Bereichs
      return false;
    } else if (a[mitte]==gesucht) {
      return true;
    } else if (a[mitte]>gesucht) {
      return interpol1(a,gesucht,von,mitte-1);
    } else {
      return interpol1(a,gesucht,mitte+1,bis);
    }
  } else {
    return a[bis]==gesucht; // true ist nur bei Aufruf mit 1 breitem Intervall möglich
    // sonst war gesucht vorher schon am Rand des Intervalls und wurde gefunden
  }
}